[프로그래머스] Lv.3 보석 쇼핑 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/67258
• 2020 카카오 인턴십 Lv.3 문제
• 🔑 : 딕셔너리, 투포인터

 

def solution(gems):

    gems_len = len(set(gems))  # 보석 종류 수
    answer = [1, len(gems)]
    gems_dict = {gems[0] : 1}  # 첫 번째 보석 미리 저장

    l = 0
    r = 0

    while l < len(gems):
        if len(gems_dict) != gems_len:  # 모든 보석이 안 들어있으면
            r += 1                      # 오른쪽으로 이동
            if r == len(gems):          # 범위 벗어나면 브레이크
                break
            if gems[r] not in gems_dict:   # 딕셔너리에 보석이 없으면 추가
                gems_dict[gems[r]] = 1
            else:
                gems_dict[gems[r]] += 1    # 있으면 갯수 증가
        else:                           # 모든 보석이 들어있으면
            if r - l < answer[1] - answer[0]:  # 더 짧은 구간인지 비교
                answer = [l+1, r+1]            # 더 짧으면 갱신
            
            if gems_dict[gems[l]] > 1:      # 제일 왼쪽 보석이 1개보다 많으면
                gems_dict[gems[l]] -= 1     # 하나씩 뺀다.
            else:                           # 1개면 딕셔너리에서 제거
                del gems_dict[gems[l]]
            l += 1                          # 왼쪽 포인터 오른쪽으로 이동

    return answer