문제
접근
처음에 방향을 잘못 잡아서 조금 돌아갔다.
시작과 끝쪽에 포인터를 하나씩 두고 이동한다면 O(n) 안에 탐색할 수 있는 것 같다.
투포인터 알고리즘이라고 한다.
우선 시작점 s와 끝점 e를 모두 0에 둔다.
e를 하나씩 옮기며 해당 점에 있는 보석을 담아준다.
모든 종류의 보석이 담기면 이제 s을 하나씩 이동하며 해당 점의 보석을 빼준다.
이 때 해당 보석을 뺏을 때 모든 보석 종류가 유지되지 않는 순간이 0~e 까지중 최소 구간이 된다.
정확히는 해당 지점의 보석이 1개가 되는 순간 그 보석을 제거하면 모든 종류를 유지할 수 없어진다.
이제 이걸 코드로 구현하면 된다.
set을 이용하여 보석의 종류를 찾고, 딕셔너리를 이용해서 보석별 개수를 카운팅해준다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def solution(gems):
all_type = list(set(gems))
dic = dict.fromkeys(all_type,0)
now_type = set()
ans = len(all_type)
min_len = 987654321
start_idx = 0
end_idx = 0
answer = []
while end_idx != len(gems):
now_type.add(gems[end_idx])
dic[gems[end_idx]]+=1
if len(now_type) == ans:
while True:
if dic[gems[start_idx]] > 1:
dic[gems[start_idx]] -= 1
start_idx += 1
else:
if min_len > end_idx-start_idx+1:
answer = [start_idx+1, end_idx+1]
min_len = end_idx-start_idx+1
dic[gems[start_idx]] -= 1
now_type.remove(gems[start_idx])
start_idx += 1
break
end_idx += 1
return answer