문제 링크

풀이 과정

• 기존 방식
  • 첫 번째 진열대부터 시작하여, 순서대로 보석을 구매
  • 최초로 모든 종류의 보석을 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