🧩 문제 접근 방식

이 문제는 모든 보석 종류를 포함하는 가장 짧은 구간을 찾는 것이 핵심입니다.
이를 효율적으로 해결하기 위해 슬라이딩 윈도우와 투 포인터라는 알고리즘 개념을 사용했습니다.

🔸 슬라이딩 윈도우 란?

연속된 구간을 다루는 문제에서 효율적으로 접근하기 위한 기법입니다.

구간의 시작과 끝을 조절하며(한 포인터는 구간 확장, 다른 포인터는 구간 축소) 탐색합니다.

이 방식은 구간의 크기를 유동적으로 변경할 수 있어, 반복되는 부분을 최소화하고 효율적으로 문제를 해결할 수 있습니다.

🔸 투 포인터 란?

정렬된 배열이나 부분 구간 문제에서 주로 활용되는 방식입니다.

서로 다른 위치에서 시작하는 두 포인터가 조건에 맞게 이동하면서 구간을 탐색합니다.

이 방식은 구간을 고정하지 않고, 두 포인터를 이동시키면서 필요한 조건을 만족하는 값을 찾습니다. 조건에 따라 포인터를 왼쪽이나 오른쪽으로 이동시켜 최적의 구간을 찾는 데 유용합니다.

from collections import defaultdict

def solution(gems):
    u_gem = len(set(gems)) # 중복을 제거하고 난 보석 종류 수
    gem_value = defaultdict(int) # 보석의 개수를 셀 defaultdict
    
    answer = [0, len(gems)-1] # 답의 초깃값
    left = 0 # 왼쪽 포인터
    min_length = len(gems) # 최소길이 초기화
    
    # 오른쪽 포인터를 한 칸씩 이동하면서 구간을 확장
    for right in range(len(gems)):
        gem = gems[right]
        gem_value[gem] += 1 # 현재 보석을 딕셔너리에 갯수 추가
        
        # 현재 구간에 모든 종류의 보석이 포함되었는지 확인
        while len(gem_value) == u_gem:
            if right - left < min_length:
                min_length = right - left
                answer = [left + 1, right + 1]
            
            # 왼쪽에 있는 보석을 줄이면서 구간을 좁힌다.
            gem_value[gems[left]] -= 1
            # 갯수가 0이되면 딕셔너리에서 삭제
            if gem_value[gems[left]] == 0:
                del gem_value[gems[left]]
            left += 1
 
    return answer

✅ 왜 defaultdict를 사용하는가?

from collections import defaultdict

defaultdict는 파이썬의 collections 모듈에 포함된 자료형으로, 존재하지 않는 키에 접근해도 기본값을 자동으로 설정해 줍니다.

딕셔너리(dict)는 없는 키에 접근하면 KeyError가 발생합니다.

my_dict = {}
my_dict['apple'] += 1  # KeyError 발생

하지만 defaultdict는 아래와 같이 자동으로 해결해 줍니다.

from collections import defaultdict

my_dict = defaultdict(int)
my_dict['apple'] += 1  # 기본값이 0이라서 0 + 1 = 1이 됨
print(my_dict['apple'])  # 1 출력

✅defaultdict 자료형 별 기본값 정리

자료형	기본값	예시
int	0	숫자 세기
list	[]	리스트로 항목 모으기
set	set()	중복 없는 값 모으기

중복을 제거하여 유일한 보석(u_gem) 개수를 뽑아내기 위해 len(set(gems))을 사용했습니다.
현재 슬라이딩 윈도우 범위 안에 있는 보석의 개수를 저장하는 딕셔너리(gem_value)에 defaultdict(int)로 선언해서, 키가 없으면 자동으로 0으로 시작하게 합니다.

def solution(gems):
    u_gem = len(set(gems)) # 중복을 제거하고 난 보석 종류 수
    gem_value = defaultdict(int) # 보석의 개수를 셀 defaultdict
    
    answer = [0, len(gems)-1] # 답의 초깃값
    left = 0 # 왼쪽 포인터
    min_length = len(gems) # 최소길이 초기화

✨ 마무리 정리

슬라이딩 윈도우: 연속된 구간에서 구간을 확장, 축소하면서 유동적으로 탐색
투 포인터: 정렬된 배열에서 두 포인터를 적절히 활용하여 구간을 유동적으로 탐색
defaultdict: 값 세기와 누적에 유용한 딕셔너리 확장

해당 문제를 통해 defaultdict와 슬라이딩 윈도우, 투 포인터에 대해 배울 수 있었습니다.

📌 아직 배우는 중이라 부족한 부분이 있을 수 있습니다.
혹시 잘못된 내용이나 더 나은 방법이 있다면 알려주세요 🙏
감사합니다! 😄