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

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

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

 

start 와 end 를 0 으로 잡고 조건을 잘 설정하여 1 씩 늘려준다. 모든 보석을 포함하는 구간을 만족했을 때 비교하여 길이가 최소가 되는 구간을 찾는다.

 

from collections import defaultdict

def solution(gems):
    answer = []
    N = len(set(gems))
    dic = defaultdict(int)
    dic[gems[0]] = 1
    start, end = 0, 0
    m = len(gems) + 1   

    while start < len(gems) and start <= end:
        if N != len(dic):
            end += 1
            
            if end == len(gems):
                break
            
            dic[gems[end]] += 1
        else:
            if N == len(dic) and m > end - start:
                m = end - start
                answer = [start+1, end+1]
            
            dic[gems[start]] -= 1
            
            if dic[gems[start]] == 0:
                del dic[gems[start]]
            
            start += 1
        
    return answer
    
    print(solution(['DIA', 'RUBY', 'RUBY', 'DIA', 'DIA', 'EMERALD', 'SAPPHIRE', 'DIA'])) # [3, 7]