https://programmers.co.kr/learn/courses/30/lessons/67258

---

1. 전체 코드

from collections import Counter


def solution(gems):
    answer = []
    s = list(set(gems))
    # 필요한 보석의 개수
    count = len(s)
    need = Counter(s)
    left = 0
    # 오른쪽 포인터 증가
    for right, j in enumerate(gems):
        if need[j] > 0:
            count -= 1
        need[j] -= 1
        # 모든 보석을 적어도 1개 이상씩 보유
        if count == 0:
            # 왼쪽 포인터 감소, 왼쪽 포인터의 보석은 항상 need값이 0이어야 한다.
            while left < right and need[gems[left]] != 0:
                need[gems[left]] += 1
                left += 1
            answer.append([left+1, right+1, right - left + 1])
            need[gems[left]] += 1
            count += 1
            left += 1
    s = sorted(answer, key=lambda x: (x[2], x[0]))
    return s[0][0:2]

---

2. 후기

우측으로 이동하는 슬라이딩 윈도우를 사용하고, 조건을 만족시키는 위치에 도착했을 때 좌측 포인터의 크기를 감소시켜 가장 짧은 길이를 갖는 최적의 값을 찾아야 한다.

2-1. 해석

초기의 need값은 Counter({'EMERALD': 1, 'DIA': 1, 'RUBY': 1, 'SAPPHIRE': 1})이다. 모든 보석이 한개씩 필요한 상태이다. 아래 예시를 통해 Counter값의 의미를 알아보자.

형광팬으로 칠해진 부분은 배열을 탐색중인 윈도우의 범위를 의미하며 left는 0, right는 6인 상태이다. 이 때 need는 Counter({'SAPPHIRE': 0, 'EMERALD': 0, 'RUBY': -1, 'DIA': -2}) 이다.

SAPPHIRE: 0 -> 잉여 X
EMERALD: 0 -> 잉여 X
RUBY: -1 -> 잉여 RUBY가 1개 더 존재한다.
DIA: -2 -> 잉여 DIA가 2개 더 존재한다.

            # 왼쪽 포인터 감소, 왼쪽 포인터의 보석은 항상 need값이 0이어야 한다.
            while left < right and need[gems[left]] != 0:
                need[gems[left]] += 1
                left += 1

위 과정을 거치면 위와같이 윈도우의 범위가 감소된다. 왼쪽 포인터에 해당하는 보석은 항상 잉여 보석이 없는 보석으로 설정해야 최소 길이를 찾을 수 있다.