[프로그래머스] 보석 쇼핑(Python)

투 포인터로 해결해야할 것 같긴한데, 아이디어가 떠오르지 않아 다른 분의 문제풀이를 참고했다. 해당 글의 핵심을 아래와 같이 이해했다.

구간[a, b]에서 모든 종류의 보석을 살 수 있을 때부터 a+=1를 한다.(i.e. 구간의 범위가 좁아졌다.) 그리고 모든 범위의 보석을 살 수 있는지 본다. 살 수 있으면 살 수 없을 때 까지 계속 좁혀본다. 반대로, 좁혀진 범위의 구간에서 모든 종류의 보석을 살 수 없으면, b+=1을 하여 구간의 범위를 넓힌 후, 모든 종류의 보석을 살 수 있는지 확인한다. 이 과정을 a가 n 또는 b가 n이 될때까지 반복한다.(n은 보석개수)

위의 과정에서 얻은 구간 중 최소 구간을 구하면된다. 아이디어를 토대로 구현했는데 중간에 꼬여서 어떤 TC에서 a>b (아래의 코드에서는 lp > rp)일 때가 존재한다.(e.g.['ruby', 'ruby', 'ruby']) 정답처리 받았지만 그래도 내 코드보다는 위의 링크를 참고해서 푸는 것을 권장한다.

1. 코드

from collections import defaultdict

def solution(gems):
    size = len(gems)
    kinds = len(set(gems))
    d = defaultdict(int)
    lp, rp = 0, 0
    answer = [0, int(1e9)]
    count = 0
    has_all_kind = False

    while lp < size and rp < size:
        if not has_all_kind:
            if not d[gems[rp]]: count += 1
            d[gems[rp]] += 1
        
        if count == kinds:
            d[gems[lp]] -= 1
            if not d[gems[lp]]: count -= 1           
            answer = min(answer, [lp+1, rp+1], key=lambda x: abs(x[0]-x[1]))
            lp += 1
            has_all_kind = True
            continue
            
        has_all_kind = False
        rp += 1
            
    return answer