[프로그래머스 Lv.3] 보석 쇼핑 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/67258

프로그래머스

풀이

투포인터를 사용한 풀이이다. 시작 포인터와 끝 포인터를 두고, 그 포인터 사이에 위치한 보석들의 종류가 주어진 조건을 만족하는지 확인하며 두 개의 포인터를 조절해가며 최소 길이의 범위를 찾으면 되는 문제이다.

 

두 개의 포인터 모두 인덱스 0에서 시작한다. 만약 두 포인터 사이에 위치한 보석의 종류가 모든 보석의 종류보다 적다면, 끝 포인터를 1 증가시켜 사이에 위치한 보석의 수를 증가시킨다. 계속 증가시키다가 모든 보석의 종류의 수를 넘어서게 된다면, 이번엔 시작 포인터를 1 증가시켜 사이에 위치한 보석의 수를 감소시킨다. 또한 동시에 현재 구간의 길이가 이전까지 조건을 만족하는 길이보다 더 짧다면, 해당 부분을 정답으로 업데이트하는 작업도 진행한다.

위의 과정을 끝 포인터가 전체 보석의 수를 넘어설 때까지 반복하면, 원하는 최소 길이의 구간을 얻을 수 있다.

from collections import defaultdict

def solution(gems):
    start, end = 0, 0 # 시작, 끝 포인터
    
    kind = len(set(gems)) # 모든 보석의 종류의 수
    length = len(gems) # 전체 보석의 수
    
    answer = [0, length-1] # 우선 전체 구간으로 설정해두고, 더 짧은 조건을 만족하는 구간이 나타나면 업데이트하도록 함
    
    dic = defaultdict(int) # 두 포인터 사이의 보석의 종류를 담을 딕셔너리
    dic[gems[start]] += 1 # 0 위치의 보석을 담음
    
    while end < length: # 끝 포인터가 전체 보석의 수를 넘어서지 않는다면 반복
        if len(dic) < kind: # 모든 보석의 종류를 채우지 못했다면
            end += 1 # 끝 포인터를 1 증가시킴
            if end == length: # 만약 전체 보석의 수를 넘어섰다면
                break # 종료
            dic[gems[end]] += 1 # 보석을 딕셔너리에 추가
        
        else: # 모든 보석의 수를 채웠다면
            if end - start < answer[1] - answer[0]: # 현재 구간의 길이가 이전까지의 최소값보다 짧다면
                answer = [start, end] # 정답을 최소 구간으로 업데이트
                
            if dic[gems[start]] == 1:  # 구간을 줄임으로써 제거할 보석이 원래 1개만 남아있었다면 
                del dic[gems[start]] # 딕셔너리에서 제거
            else: # 1개 초과라면
                dic[gems[start]] -= 1 # 보석의 수를 1개 줄임
            start += 1 # 시작 포인터 증가
        
    return [answer[0] + 1, answer[1] + 1] # 보석 번호는 배열의 인덱스와 다르게 1부터 시작하기에 +1 해줌