[카카오 인턴] 보석 쇼핑

Pointer 두개를 사용하여, 각각의 위치를 변화시켜가며 최적의 결과를 도출해내는 유형이다. 최적의 구간을 찾을 때 활용하기 좋다.

이때 중요한 부분은 '왼쪽, 오른쪽 각각의 포인터가 언제 업데이트 되는가', '포인터가 어디에서 시작하는가'이다.

처음 풀었을 때 dict안에 있는 모든 key에 대해서 값이 0인지 아닌지 확인해 나가면서 진행하였는데 이렇게 하면 시간이 초과가 된다. 이를 해결 하려면 '모든 보석이 있는가?' 를 확인하기 위해서 dict 안에 들어있는 key의 개수를 확인하는 것이 좋다. 이렇게 하면 O(1) 이니 훨씬 빠르게 할 수 있다 >> 결론적으로 key 값의 유무로 있는지 없는지를 확인할 수 있다.

*추가적으로 list를 기반으로 구현한 라이브러리들은 in, del, append, pop등 유사한 메소드를 가지고 있는 경우들이 많다.

from collections import defaultdict

def solution(gems):
    d = defaultdict(int)
    for i in set(gems):
        d[i] = 0
    max_gem = len(d.keys()) # gem의 종류의 수를 미리 저장
    
    min_pointer_distance = len(gems) # 구간 최소거리 
    l = 0 # left pointer
    r = 0 # right pointer
    
    # 이전 포인터들의 위치를 기억. 한번에 업데이트 해주기 위해서 저장 
    pre_l = l 
    pre_r = r
    
    #return 할 답
    answer_l = 0
    answer_r = 0
    
    d = defaultdict(int)
    d[gems[l]] += 1 #첫번째는 미리 넣어주기 
    
    while r < len(gems):
        # 업데이트
        if pre_l != l:
            d[gems[pre_l]] -= 1
            if d[gems[pre_l]] == 0:
                del d[gems[pre_l]] # 만약 보석의 개수가 0이라면 key 값 제거 
            pre_l = l
        elif pre_r != r:
            pre_r = r
            d[gems[pre_r]] += 1
        
        if r-l > min_pointer_distance: # 만약 구간의 길이가 기존보다 크다면, 구간 거리 감소를 위해 l을 이동
            l += 1
        elif len(d) == max_gem: # 모든 보석이 있다면 >> 왼쪽 증가
            if r-l < min_pointer_distance:
                min_pointer_distance = r - l
                answer_l = l + 1
                answer_r = r + 1
            l += 1
        else: #뭣도 아니면 오른쪽 증가 
            r += 1
            
    return [answer_l, answer_r]

print(solution(["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]))