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

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

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

 

투 포인터 문제다. 처음에 set을 이용해서 각각의 경우마다 set(gems[start : end +1]) == set(gems) 이렇게 풀었었는데,

효율성 테스트에서 시간 초과가 났다.

 

시간초과가 날 때 입력 값의 범위를 고려해서 알고리즘을 변경하거나

set or dict를 활용할 생각을 해야겠다.

 

나의 풀이

def solution(gems):
    start, end, answer = 0, 0, [0, len(gems)-1]
    jewel_kinds = len(set(gems))
    jewel = {gems[0]:1}
    
    while start < len(gems) and end < len(gems):
        if len(jewel) == jewel_kinds:
            if answer[1] - answer[0] > end - start:
                answer = [start,end]
            if jewel[gems[start]]>1:
                jewel[gems[start]] -=1
            else:
                del(jewel[gems[start]])
            start+=1
        else:
            end += 1
            if end == len(gems):
                break
            if gems[end] not in jewel:
                jewel[gems[end]] = 1
            else:
                jewel[gems[end]] +=1
    return [answer[0]+1, answer[1]+1]