보석쇼핑

문제

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

접근방식

투포인터 알고리즘 활용 문제다.

이렇게 배열의 연속된 구간을 다루는 문제는 투포인터 알고리즘을 쓰면 좋다. 투포인터 알고리즘은 두 개의 포인터를 늘려가며 이에 따라 해당 구간의 값을 수정해가며 최적의 해를 구하는 방식으로, 대표적인 문제로 부분합 문제가 있다.
https://www.acmicpc.net/problem/1806

코드

"""
1. set(gems) - 종류
2. l, r 늘려가며 dictionary 갱신!
"""
#투포인터 알고리즘
def solution(gems):
    length = len(set(gems))
    l, r, min_len = 0, 0, float('inf')
    min_range = [0, 0]
    cur_map = dict()
    cur_map[gems[0]] = 1
    while r < len(gems) and l <= r:
        if len(cur_map) == length:
            if r + 1 - l < min_len: 
                min_len = r + 1 - l
                min_range = [l + 1, r + 1]
        if len(cur_map) < length and r + 1 < len(gems):
            r += 1
            if gems[r] in cur_map: cur_map[gems[r]] += 1
            else: cur_map[gems[r]] = 1
        else:
            if cur_map[gems[l]] == 1: del cur_map[gems[l]]
            else: cur_map[gems[l]] -= 1
            l += 1         
    return min_range