[프로그래머스] 보석 쇼핑 - Python

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

프로그래머스

---

• 풀이
  • 한 개씩 추가하면서 그 구간에 보석 종류가 다 있는지 체크
  • 다 있다면 answer 리스트에 추가
    • 이 구간에서 맨 앞 보석을 빼도 보석 종류가 다 있는지 체크
    • 반복
  • Counter
    • value에 +1을 하고 싶을 때 key가 없다면 key 생성(value가 0인)
    • dict는 key가 없는 경우 +1이 안됨
• 코드

from collections import Counter

def solution(gems):
    # 진열대에 있는 보석 종류
    n = len(set(gems))
    
    # 정답이 될 수 있는 구간들
    answer = []
    # 구간의 맨 앞
    start = 0
    jewel_cnt = Counter()
    
    for i in range(len(gems)):
        jewel_cnt[gems[i]] += 1
        
        # 모든 보석이 1개씩 다 있는가?
        while n == len(jewel_cnt):
            answer.append([start+1,i+1])
            # 범위의 맨 앞 보석빼보자
            jewel_cnt[gems[start]] -= 1
            if jewel_cnt[gems[start]] == 0:
                del jewel_cnt[gems[start]]
            start += 1
            
    # 짧은 구간이면서 시작 번호가 작은 순으로
    answer.sort(key=lambda x:((x[1]-x[0]),x[0]))
    return answer[0]