gems 배열 크기는 최대 100,000 이기 때문에 O(N^2)으로 풀면 시간 초과가 난다.
따라서 start, end 두개의 포인터를 조작하는 투포인터 알고리즘을 활용
보석의 종류별로 최소 1개 이상의 수량이 있을 때까지 right를 1씩 더해줌
최소 1개 이상의 수량이 확보되었으면 left를 1씩 움직여가며 중복된 보석을 제거해줌
gems 배열 끝까지 위 단계를 반복해 cand 배열에 넣은 후 구간 길이가 짧고, 같다면 left 크기가 작은 원소를 리턴한다.
코드
from collections import defaultdict
def solution(gems):
cand = []
left=right=0
N, gem_num = len(gems), len(set(gems))
dic = defaultdict(int)
while left<=right:
# len(dic)은 dic의 key 값의 수, gem_num은 보석의 종류, 즉 두개가 같아야 left를 움직여줌
if len(dic) == gem_num:
# dic[gems[left]] ==1이란 뜻은 해당 left 위치에서 더이상 움직일 수 없다는 뜻(최소 1개 수량 확보 불가능)
if dic[gems[left]] ==1:
cand.append((left+1, right, right-left))
del dic[gems[left]]
else :
dic[gems[left]] -=1left+=1else:
if right== N :
break
dic[gems[right]] +=1right+=1
cand.sort(key = lambda x: (x[2], x[0]))
return cand[0][:2]