문제 링크
풀이 과정
•
기존 방식
◦
첫 번째 진열대부터 시작하여, 순서대로 보석을 구매
◦
최초로 모든 종류의 보석을 1개 이상 포함할 때, 탐색 종료 및 구간 업데이트
◦
시작 지점을 1씩 증가시키면서, 위 동작을 반복 → 최소 길이의 구간을 찾아야하므로
◦
시간 복잡도는 O(N^2)이고, 배열의 크기 N은 최대 100,000이므로, 시간 초과가 발생할 수 있습니다.
•
개선된 방식
◦
리스트 문제에서 쉽게 떠올릴 수 있는 투 포인터를 이용해봅시다.
◦
start, end = 첫 번째 진열대로 초기화합니다.
◦
최초로 모든 종류의 보석을 1개 이상 포함할 때까지, end 값을 1씩 증가시킵니다.
▪
이때, 딕셔너리 자료 구조를 활용합니다 → {보석이름: 갯수}
▪
현재까지 구매한 보석과 그 갯수를 기억하는 데 가장 적합한 자료구조로 생각하기 때문입니다!
◦
이제는, start를 1씩 증가시키면서, 모든 종류의 보석을 1개 이상 포함하는 지 확인합니다.
▪
문제에서 요구하는 것은 최소 길이의 구간이기 때문입니다.
▪
기존에 start 지점에 위치한 보석의 갯수를 1만큼 차감합니다.
•
(주의) 보석의 갯수가 0인 경우, 딕셔너리에서 제거해야합니다!!
•
현재 시점에서 우리가 가지고 있는 보석의 종류 수를 구하기 때문입니다!!!
전체 코드
def solution(gems):
gem = list(set(gems))
n = len(gem)
dic = {gems[0]: 1}
answer = [1, len(gems)]
start, end = 0, 0
while start <= end and end < len(gems):
if len(dic) == n:
# 비교 연산자가 >= 가 아닌 > 임에 주목하세요!
# 구간의 길이가 같아도, start 값이 작은 진열대를 먼저 탐방하므로, 구간을 갱신하지 않습니다.
if answer[1]-answer[0] > end - start: answer = [start+1, end+1]
dic[gems[start]] -= 1
if dic[gems[start]] == 0: del dic[gems[start]]
start += 1
elif len(dic) < n:
end += 1
if end >= len(gems): break
dic[gems[end]] = dic.get(gems[end], 0) + 1
return answer
Python
복사