보석 쇼핑*

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

코딩테스트 연습 - 보석 쇼핑

 

해결 방법 : 투 포인터

• 모든 보석 종류를 포함하는 최소의 진열대 길이를 구해야한다.
  • 먼저 모든 종류의 보석이 담길때까지 진열대에 있는 보석을 순서대로 가져온다.
  • 모든 보석 종류를 포함하게 되면 가장 먼저 집은 보석부터 덜어내보며 구간을 줄여본다.
  • 반복 
  • 반복 조건을 잘 생각할 필요가 있다.
    • 우선 right가 아직 진열대 끝까지 탐색하지 못했다면 계속 탐색할 필요가 있다.
    • right가 진열대 끝까지 간 상태에서 모든 종류의 보석을 포함하고 있다면, left를 비워내며 최소 구간이 갱신될 가능성이 있으므로 계속 탐색해야 한다.
• 보석 종류를 모두 포함한 경우에는 현재 상황이 최소 구간인지 지속적으로 확인하며, 맞다면 갱신한다.

 

from collections import defaultdict

def solution(gems):
    answer = [0, float('inf')]
    N = len(gems) # 진열대 길이
    num_gems = len(set(gems)) # 보석 종류 개수
    gem_stat = defaultdict(int) # 현재 보석 통계
    
    l, r = 0, 0 # 투 포인터
    while r <= N - 1 or (r == N and len(gem_stat) == num_gems): # 진열대 끝까지 또는 진열대 끝이면서 보석이 모두 담겼을때
        if len(gem_stat) < num_gems: # 보석을 더 담아봐야한다
            gem_stat[gems[r]] += 1
            r += 1
            
        else: # 이미 모든 종류의 보석을 가지고 있으므로 담겨있는 첫번째 보석을 덜어본다.
            gem_stat[gems[l]] -= 1 
            if gem_stat[gems[l]] == 0:
                del gem_stat[gems[l]]
            l += 1
        # 보석 종류를 모두 가지면서 더 짧은 구간을 찾았을 경우 갱신    
        answer = [l + 1, r] if len(gem_stat) == num_gems and r - l - 1 < answer[1] - answer[0] else answer
    
    return answer

 

 

이전 풀이와 비교

: 같다.