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

코드

from collections import defaultdict

def solution(gems):
    start = 0  # 부분리스트 시작점
    end = len(gems) -1  # 부분리스트 끝점
    tracker = defaultdict(int)  # 부분리스트가 가지고있는 원소의 개수
    for gem in gems:
        tracker[gem] += 1
    while tracker[gems[end]] > 1:
        tracker[gems[end]] -= 1
        end -= 1
    while tracker[gems[start]] >1 :
        tracker[gems[start]] -= 1
        start += 1
    length = end - start 
    ret = (start, end)
    while end < len(gems) - 1:
        end += 1
        tracker[gems[end]] += 1
        while tracker[gems[start]] > 1:
            tracker[gems[start]] -= 1
            start += 1
        if (end - start) < length:
            length = end - start
            ret = (start, end)
    return [i+1 for i in ret]
    

내가 푼 방법

처음에 모든 원소를 가지고 있으면서, 끝점이 가장 왼쪽에 있고, 최대한 개수가 적은 리스트 하나를 도출한다.
끝점을 하나씩 오른쪽으로 옮기면서 시작점을 최대한 오른쪽으로 땡기고, 원소개수가 최소가 되면 ret을 업데이트 한다.

처음 문제를 봤을땐 부분리스트의 최소 배열이 전체 리스트의 최소배열이라는 점에서 착안하여 재귀와 DP를 써서 왼쪽 하나 지우고, 오른쪽 하나 지우며 최소배열을 도출하려고 했는데 시간초과가 나거나 재귀호출 제한에 걸렸다.

배운것

부분리스트가 항상 모든 원소를 가진다는 무결성을 유지하면서 리스트를 순회하며 어떤 끝점에서 가장 작은 리스트를 구하는것이 가능했다.