문제 설명
•
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매하는 방법을 출력하는 문제
예제 입력/출력
gems | result |
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] | [3, 7] |
["AA", "AB", "AC", "AA", "AC"] | [1, 3] |
["XYZ", "XYZ", "XYZ"] | [1, 1] |
["ZZZ", "YYY", "NNNN", "YYY", "BBB"] | [1, 5] |
제약 조건
•
문제 풀이
•
접근1 투 포인터 -
◦
투 포인터 알고리즘을 사용하여 보석 종류를 모두 포함하는 가장 짧은 구간을 찾는 방법
▪
left와 right 두 개의 포인터를 활용하여 범위를 조정하면서 최적의 구간을 탐색
◦
접근 방법
1.
set 자료구조를 사용하여 보석의 총 종류 수(kind)를 계산한다.
2.
dict 자료구조를 사용하여 보석의 개수를 관리한다.
3.
left와 right 포인터를 모두 1번 진열대에 위치시킨다.
4.
양 포인터가 가르키는 범위 안에 포함된 보석 종류의 개수를 세어본다.
a.
범위 안의 보석 종류가 전체 보석 종류보다 부족하다면 right 포인터를 증가시킨다.
b.
범위 안의 보석 종류가 전체 보석 종류와 일치하면 left 포인터를 증가시킨다.
◦
즉, 왼쪽을 가리키는 포인터 left와 오른쪽을 가리키는 포인터 right를 이용하여 보석의 종류가 모자라면 right을 증가시키고, 보석의 종류가 충분하면 left를 증가시키는 과정을 반복하면서 정답을 갱신시켜나간다.
◦
이때, left를 증가시키기 전에 dict 자료구조에서 left번 진열대에 있던 보석의 빈도수를 감소시켜주어야 하며 특히 빈도수가 1에서 0이 될 때에는 dict에서 완전히 제거하여야 한다.
◦
right를 증가시킬 때는 dict 자료구조에서 증가된 right번 진열대에 있는 보석의 빈도수를 증가시켜주어야 하며 특히 right가 인덱스 범위를 벗어나지 않도록 신경써준다.
풀이 코드
from collections import defaultdict
def solution(gems):
n = len(gems)
answer = [1, n + 1]
kind = len(set(gems))
gem_dict = defaultdict(int)
gem_dict[gems[0]] += 1
# 투 포인터
left, right = 0, 0
while left < n and right < n:
# 보석의 개수가 부족한다면 right 포인터 증가
if len(gem_dict) < kind:
right += 1
if right < n: # Index 에러 방지
gem_dict[gems[right]] += 1
# 보석의 개수가 충분하다면 left 포인터 증가
else:
if right - left < answer[1] - answer[0]:
answer = [left + 1, right + 1]
if gem_dict[gems[left]] == 1:
del gem_dict[gems[left]]
else:
gem_dict[gems[left]] -= 1
left += 1
return answer
Python
복사