[programmers/py] 보석 쇼핑

보석 쇼핑

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

문제 설명

• 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
• 가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

문제 풀이

• dict를 사용해서 각 보석의 수를 추가
• dict의 길이와 보석 수가 같으면 배열(arr)에 추가 후 left + 1

from collections import defaultdict
def solution(gems):
    answer = []
    left = 0
    num = len(set(gems))
    d = defaultdict(int)
    for right in range(len(gems)):
        d[gems[right]] += 1
        right += 1

        while len(d) == num:
            d[gems[left]] -= 1
            if d[gems[left]] == 0:
                del d[gems[left]]
            left += 1
            answer.append([left, right])

    return sorted(answer, key = lambda x: (x[1]-x[0], x[0]))[0]