프로그래머스 보석 쇼핑, 파이썬

문제

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

해결 방법

투포인터 알고리즘을 사용해야 한다.

코드

def solution(gems):
    answer = []
    shortest = len(gems) + 1 # 현재 최단 구간 길이
    
    s, e = 0, 0 # 투포인터 (시작, 끝)
    
    check_len = len(set(gems)) # 보석 종류 수
    contained = {} # 현재 구간에 포함된 보석들(종류: 수)
    
    while e < len(gems):
        if gems[e] not in contained:
            contained[gems[e]] = 1
        else:
            contained[gems[e]] += 1
        e += 1
        
        if len(contained) == check_len:
            while s < e:
                if contained[gems[s]] > 1:
                    contained[gems[s]] -= 1
                    s += 1
                elif shortest > e - s:
                    shortest = e - s
                    answer = [s + 1, e]
                    break
                else:
                    break
    
    return answer