[python] 프로그래머스 보석 쇼핑

프로그래머스 보석 쇼핑

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

문제

풀이

def solution(gems):
    gem_types = len(set(gems))  # 보석 종류의 개수
    gem_dict = {}  # 현재 구간에 포함된 보석의 개수를 기록할 딕셔너리
    answer = [0, len(gems) - 1]  # 최소 구간의 시작과 끝 인덱스 저장
    left = 0  # 윈도우의 왼쪽 포인터
    min_len = len(gems)  # 최소 구간 길이
    
    for right in range(len(gems)):  # 윈도우의 오른쪽 포인터 이동
        gem = gems[right]
        if gem in gem_dict:
            gem_dict[gem] += 1
        else:
            gem_dict[gem] = 1
        
        # 현재 구간에 모든 보석이 포함될 때까지 윈도우의 왼쪽 포인터 이동
        while len(gem_dict) == gem_types:
            # 현재 구간의 길이가 더 짧으면 갱신
            if right - left < min_len:
                min_len = right - left
                answer = [left + 1, right + 1]  # 인덱스는 1부터 시작이므로 +1
            
            # 왼쪽 포인터 이동
            gem_dict[gems[left]] -= 1
            if gem_dict[gems[left]] == 0:
                del gem_dict[gems[left]]
            left += 1
    
    return answer

📌 보충설명

예시 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]를 가지고 코드를 살펴보자.

일단 left, right 둘 다 0 에서 시작.

for right in range(len(gems)):  # 윈도우의 오른쪽 포인터 이동
        gem = gems[right]
        if gem in gem_dict:
            gem_dict[gem] += 1
        else:
            gem_dict[gem] = 1

모든 보석들을 포함할 때까지 right을 옮긴다. 즉 여기서는 맨 마지막에 있는 다이아 이전, 7번을 가르키게 된다. 그러면 answer 는 아직 [1, 7] 이 된다.

# 현재 구간에 모든 보석이 포함될 때까지 윈도우의 왼쪽 포인터 이동
   while len(gem_dict) == gem_types:
       # 현재 구간의 길이가 더 짧으면 갱신
       if right - left < min_len:
           min_len = right - left
           answer = [left + 1, right + 1]  # 인덱스는 1부터 시작이므로 +1
       
       # 왼쪽 포인터 이동 (구간 축소)
       gem_dict[gems[left]] -= 1
       if gem_dict[gems[left]] == 0:
           del gem_dict[gems[left]]
       left += 1

그 후, while len(gem_dict) == gem_types: 이게 진짜 생각하기 어려운데, 모든 보석을 포함한다면 계속해서 left 포인터를 통해 범위를 줄여나간다.

왼쪽 보석 gems[left]는 dia 가 되고, dia 는 지금 3개였는데 2개로 줄인다. 구간에 여전히 4가지 보석이 포함되어 있으므로 left 포인터를 한 칸 더 이동한다.
그 다음 gems[left] 는 ruby 가 된다. 이거도 2개에서 1로 줄인다.
그러면 answer 가 우선 [3,7]이 된다. 그 다음 gems[left]는 ruby이다. gem_dict 에서 루비의 개수가 0 이 되어 루비가 사라진다. 그럼 while 문에서 나오게 된다.

마지막으로 right 이 7 이 되고, 여덟 번째 보석을 확인하는데 dia 이다. 여전히 루비가 없기에 while 문이 실행되지 않고 끝이 난다.

따라서 정답은 [3,7] 이 된다.