[Python] Programmers 보석 쇼핑 (2020 카카오 인턴십)

처음에는 최적화로 DP를 활용하는 문제인가 고민해봤지만, DP를 이용하여 구간을 구하는 쉬운 방법이 떠오르지 않아 노선을 변경했다. 한 번 훑으면서 조건에 맞는 구간을 출력한다. 우선 코드 상으로 left는 구간의 시작점을 right는 구간의 끝점을 나타낸다. while()을 통해 right는 한 번 훑으면서 새로운 보석을 발견했을 때, contains라는 dict에 값을 저장한다. contain이 기존에 구한 unique 보석의 개수를 모두 충족했을 때부터 left를 변경한다. 만약 이미 한 개 이상 보석이 존재할 때 해당 구간은 여벌의 보석을 소유한 것이므로 오른쪽으로 이동하며 구간에서 제외한다.   

def solution(gems):
    left = 0; right = 0
    targets = set(gems)
    end = len(gems)
    answer = [1, end]
    length = len(targets)
    contains = {}
    
    while right < end:
        if gems[right] not in contains:
            contains[gems[right]] = 1
        else:
            contains[gems[right]] += 1
        right += 1
        if len(contains) == length:
            while contains[gems[left]] > 1:
                contains[gems[left]] -= 1
                left += 1
            if answer[1] - answer[0] > right - left-1:
                answer = [left+1, right]
            if right - left +1 == length:
                return answer
    return answer