[프로그래머스 보석 쇼핑] - 파이썬 풀이

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

프로그래머스

문제 요약

보석이 진열된 배열이 주어졌을 때, 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아라.

---

풀이

문제의 제한사항에서 gems의 길이가 최대 100,000이라고 하니, 완전탐색을 할 경우 시간초과가 발생할 위험이 있다. 따라서 다른 접근법을 생각해봐야 한다.
리스트 내의 부분리스트를 투포인터로 차례차례 탐색하면서, 만약 모든 보석을 포함하는 부분리스트를 발견할 경우 이를 answer 배열에 저장한다. 그러한 다음 answer 배열을 부분 리스트의 구간의 길이와, 시작 인덱스를 기준으로 오름차순으로 정렬한 뒤 가장 첫 번째 원소를 리턴한다.

from collections import defaultdict
def solution(gems):
    # 보석 종류의 수
    n = len(set(gems))
    answer = []
    
    # 부분 리스트의 시작 인덱스
    left = 0
    # 보석의 종류, 해당 보석이 나타난 횟수 저장
    gem_dict = defaultdict(int)
    # right을 0부터 gems의 길이까지 반복
    for right in range(len(gems)):
        # 현재 보석이 나타난 횟수 업데이트
        gem_dict[gems[right]] += 1
        # right을 증가시켜 다음 보석으로 이동
        right += 1
        
        # gem_dict의 길이가 n과 동일하다면, 
        # 모든 종류의 보석을 포함하는 부분 리스트를 찾은 것.
        while len(gem_dict) == n:
            # gem_dict[gems[left]]를 1 감소시킨다
            # 즉, 현재 보석을 부분리스트에서 시킨다.
            gem_dict[gems[left]] -= 1
            # 만약 해당 보석의 나타난 횟수가 0이 된다면,
            # 이 보석은 더이상 부분 리스트에 존재하지 않는다는 의미이므로,
            # gem_dict에서 해당 보석을 제거함.
            if gem_dict[gems[left]] == 0:
                del gem_dict[gems[left]]
            
            # 다음 부분 리스트의 시작 인덱스 이동
            left += 1
            answer.append([left, right])
    # answer를 부분 리스트의 길이, 시작 인덱스를 기준으로 정렬하고,
    # 첫 번째 원소를 반환함.
    return sorted(answer, key=lambda x: (x[1]-x[0], x[0]))[0]