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"]))