문제 요약
진열대에 보석들이 일렬로 놓여 있다.
어피치는 특정 연속 구간의 보석을 모두 구매하려고 한다.
목표는 다음과 같다.
- 모든 종류의 보석을 적어도 1개 이상 포함해야 한다.
- 가능한 가장 짧은 구간을 찾아야 한다.
- 가장 짧은 구간이 여러 개라면 시작 번호가 가장 작은 구간을 선택한다.
반환값은 1번부터 시작하는 진열대 번호 기준의 [시작, 끝]이다.
핵심 아이디어
이 문제는 모든 보석 종류를 포함하는 가장 짧은 연속 구간을 찾는 문제다.
연속 구간을 다루므로 투 포인터를 사용할 수 있다.
두 포인터를 다음처럼 관리한다.
left: 현재 구간의 시작 인덱스
right: 현재 구간의 끝 인덱스right를 오른쪽으로 이동하며 보석을 구간에 추가한다.
현재 구간이 모든 보석 종류를 포함하면, left를 오른쪽으로 이동하며 구간을 최대한 줄인다.
풀이 과정
1. 전체 보석 종류 개수 구하기
모든 종류를 포함했는지 확인하려면 전체 보석 종류 수를 알아야 한다.
total_types = len(set(gems))2. 현재 구간의 보석 개수 관리
현재 구간에 어떤 보석이 몇 개 있는지 딕셔너리로 관리한다.
gem_count = {}보석을 추가하면 개수를 1 증가시키고, 제거하면 1 감소시킨다.
개수가 0이 되면 딕셔너리에서 삭제한다.
딕셔너리의 key 개수가 total_types와 같다면 현재 구간은 모든 보석 종류를 포함한다.
3. 오른쪽 포인터 이동
right를 0부터 끝까지 이동하면서 보석을 하나씩 구간에 넣는다.
for right, gem in enumerate(gems):4. 모든 종류를 포함하면 왼쪽 줄이기
현재 구간이 모든 보석 종류를 포함하는 동안, 정답 후보를 갱신하고 left를 이동한다.
while len(gem_count) == total_types:이 과정에서 구간을 최대한 짧게 만든다.
Python 코드
def solution(gems):
total_types = len(set(gems))
gem_count = {}
left = 0
best_start = 0
best_end = len(gems) - 1
best_length = len(gems)
for right, gem in enumerate(gems):
gem_count[gem] = gem_count.get(gem, 0) + 1
while len(gem_count) == total_types:
current_length = right - left + 1
if current_length < best_length:
best_length = current_length
best_start = left
best_end = right
left_gem = gems[left]
gem_count[left_gem] -= 1
if gem_count[left_gem] == 0:
del gem_count[left_gem]
left += 1
return [best_start + 1, best_end + 1]코드 설명
전체 보석 종류 수
total_types = len(set(gems))중복을 제거한 보석 종류의 개수를 구한다.
현재 구간의 보석 종류 수가 이 값과 같다면, 모든 보석을 포함한 구간이다.
현재 구간의 보석 개수
gem_count[gem] = gem_count.get(gem, 0) + 1오른쪽 포인터가 가리키는 보석을 현재 구간에 추가한다.
gem_count는 현재 구간 안에 있는 보석별 개수를 저장한다.
모든 보석을 포함한 경우
while len(gem_count) == total_types:현재 구간이 모든 보석 종류를 포함하고 있다면, 가능한 한 왼쪽을 줄여본다.
줄이는 과정에서 계속 정답 후보를 갱신한다.
정답 갱신
if current_length < best_length:더 짧은 구간을 찾았을 때만 정답을 갱신한다.
길이가 같은 경우에는 갱신하지 않는다.
투 포인터는 왼쪽에서 오른쪽으로 진행되므로, 먼저 발견된 구간이 시작 번호가 더 작다.
왼쪽 보석 제거
left_gem = gems[left]
gem_count[left_gem] -= 1왼쪽 포인터가 가리키는 보석을 현재 구간에서 제거한다.
개수가 0이 되면 현재 구간에 해당 보석 종류가 없는 것이므로 딕셔너리에서 삭제한다.
if gem_count[left_gem] == 0:
del gem_count[left_gem]왜 투 포인터가 가능할까?
구간의 오른쪽 끝을 늘리면 포함하는 보석 종류는 유지되거나 늘어난다.
반대로 왼쪽 끝을 줄이면 구간 길이는 짧아지고, 포함하는 보석 종류는 유지되거나 줄어든다.
이처럼 구간을 확장하고 축소하는 방향이 명확하므로 투 포인터를 사용할 수 있다.
모든 보석 종류를 포함할 때마다 왼쪽을 줄이면, 각 오른쪽 끝에 대해 가능한 가장 짧은 구간을 확인할 수 있다.
시간 복잡도
left와 right는 각각 배열을 한 번씩만 지나간다.
따라서 시간 복잡도는 다음과 같다.
O(n)n은 gems의 길이다.
공간 복잡도
현재 구간의 보석 개수를 저장하는 딕셔너리를 사용한다.
보석 종류 수를 k라고 하면 공간 복잡도는 다음과 같다.
O(k)정리
이 문제는 모든 보석 종류를 포함하는 최소 연속 구간을 찾는 문제다.
핵심은 다음과 같다.
- 오른쪽 포인터로 보석을 추가한다.
- 모든 종류가 포함되면 왼쪽 포인터를 이동하며 구간을 줄인다.
- 더 짧은 구간을 찾으면 정답을 갱신한다.
- 길이가 같으면 먼저 찾은 구간을 유지한다.
투 포인터와 딕셔너리를 함께 사용하면 효율적으로 해결할 수 있다.
