[프로그래머스] 보석 쇼핑 (파이썬)

📕 문제

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

코딩테스트 연습 - 보석 쇼핑

 

💡 풀이법

1. 만약 중복을 제거한 보석의 개수(unique_l)가 1이면 바로 [1,1]을 반환한다.

2. 투포인터(start, end)를 이용한다.

3. end를 1씩 증가시키면서 탐색을 한다.

4. 매순간마다 첫번째에 있는 보석의 개수를 확인하고 1보다 크면 start 포인터를 1증가시키고 첫번째 보석의 개수를 1 감소시킨다.

5. 딕셔너리의 키값과 unique_l이 같다면 현재 범위가 모든 종류의 보석을 담고 있다는 의미이다. 이때, 가장 짧은 범위(short)와 answer를 갱신시키고, flag를 false로 바꿔준다. 

(여기서 flag는 키의 개수와 unique_l를 계속해서 비교하면 시간이 오래 걸리기 때문에 가장 처음에만 비교하도록 만든 변수이다. 한번 키의 개수가 unique_l과 같아지면 그 다음부터는 무조건 같게 되기 때문에 처음에만 확인하면 됨)

 

from collections import defaultdict
def solution(gems):
    answer = []
    l = len(gems)
    unique_l = len(set(gems))

    if unique_l == 1:
        return [1, 1]

    start, end = 0, 0
    flag = True
    dict = defaultdict(int)
    dict[gems[start]] += 1
    while end < l-1:
        end += 1
        dict[gems[end]] += 1
        while dict[gems[start]] > 1:
            dict[gems[start]] -= 1
            start += 1

        if flag:
            if len(dict.keys()) == unique_l:
                short = end-start+1
                answer = [start+1, end+1]
                flag = False
        else:
            if end - start + 1 < short:
                short = end-start+1
                answer = [start+1, end+1]

    return answer