[프로그래머스/Lv2] 보석쇼핑 - Python

https://school.programmers.co.kr/learn/courses/30/lessons/67258

프로그래머스

 

문제를 보고 백준 과일 탕후루 문제랑 비슷하다고 생각났지만(투포인터, 슬라이딩 윈도우) 왠지 그냥 비효율적으로 풀어보고싶어서 냅다 풀어봤는데 당연히 시간초과 나고 정확도 검사도 틀렸다.

 

# 실패 코드 1

def solution(gems):
    answer = []
    
    gems_set = set(gems)
    gems_dict = {g: 0 for g in gems_set}
    
    for idx, gem in enumerate(gems):
        gems_dict[gem] = idx + 1
        
        cur_value = gems_dict.values()
        if all(i != 0 for i in cur_value):
            answer = [min(cur_value), max(cur_value)]

            break
            
    print(gems_dict)
    
    
    return answer

 

문제점

1. 첫번쨰 가능한 구간을 찾고 바로 break

2. 보석이 나타날때마다 보석의 마지막 위치만 저장하고있음 (보석이 빠지거나, 중복되는 경우 발생)

 

그래서 두번째로 며칠 전 풀었던, 백준 List of Unique Numbers 문제가 생각나서 똑같이 풀었다.

 

# 성공 코드 1

from collections import defaultdict

def solution(gems):
    total = len(set(gems))  # 보석 종류의 총 개수
    left = 0
    result = [0, len(gems)]
    select = defaultdict(int)

    # 끝 점을 순회하며 최솟값 찾기
    for right in range(len(gems)):
        select[gems[right]] += 1  # 보석 추가

        # 조건이 맞으면
        while len(select) == total:
        
            # 현재 구간이 기존 최솟값이라면 갱신
            if right - left < result[1] - result[0]:
                result = [left + 1, right + 1]

            # 구간 축소하며 최솟값 찾기
            select[gems[left]] -= 1
            if select[gems[left]] == 0:
                del select[gems[left]]
                
            left += 1

    return result

 

 

그러다가 왠지 처음부터 left, right 둘다 0으로 시작해볼까라는 생각이 들어서 다시 풀어봤다.

 

# 성공 코드 2

from collections import defaultdict

def solution(gems):
    answer = []
    
    n = len(gems)
    gems_set = set(gems)
    gems_dict = defaultdict(int)
    min_length = float('inf')

    left = right = 0
    
    # 범위 벗어나기 전까지 반복
    while right < n:
        gems_dict[gems[right]] += 1 # 보석 추가
        
        # 보석 다 채웠으면
        while len(gems_dict) == len(gems_set):
        	
            # 최솟값일때 갱신
            if right - left + 1 < min_length:
                answer = [left + 1, right + 1]
                min_length = right - left + 1
            
            # 범위 축소하며 최솟값 찾기
            gems_dict[gems[left]] -= 1
            if gems_dict[gems[left]] == 0:
                del gems_dict[gems[left]]
            left += 1
        
        right += 1

    return answer

 

 

근데 풀어보니까 이거나 저거나 똑같네~

구현 방법이 많아보여서 어떻게 풀지 많이 고민했던 문제였다