Programmers - 보석 쇼핑

문제 링크

완전탐색으로 풀게 되면 시간초과가 날게 뻔해보였는데 그 이외의 방법이 떠오르지 않았다.
질문하기에서 투포인터 라는 키워드를 얻고 상세한 풀이는 보지 않고 풀었다.
(투포인터가 무엇인지는 알고 있었지만 이 문제를 봤을 때 떠오르지 않았다)

풀이 방법
1. 현재 l~r에서 모든 보석을 가지고 있으면 answer 업데이트
2. r+=1 후 r번째 gem 추가 , l번째 gem 없어도 되는 경우 l+=1 (l번째 gem이 꼭 필요할 때까지 반복)
3. r이 len(gems)에 도달 때까지 1,2를 반복

풀었을 때 시간초과가 나서 하나씩 시간을 최적화하는 과정을 거쳤다.
1) 반복문 내에서 set(gems[l:r+1]) 을 사용했었음
-> deque(current)에 l~r 까지의 gem 저장
-> 어떤 보석을 몇 개 가지고 있는지만 알면 됨 : current 제거, gem_count, gem_set로만 문제를 풀 수 있음

2) 모든 gem을 가지고 있는지 여부를 gem_count를 하나씩 순회함
-> gem이 add,remove 될 때마다 gem_count를 업데이트하고, gem_count가 0일때 gem_set에서 제거, 모든 gem을 가지고 있는 여부는 len(gem_set)으로 O(1)에 판단 가능해짐

def solution(gems):

    gem_dict = dict()
    index = 0
    for gem in gems:
        if gem_dict.get(gem) == None:
            gem_dict[gem] = index
            index += 1
    gems = list(map(lambda g: gem_dict[g], gems))
    n = len(gem_dict)
    answer = [1, len(gems)]

    l = 0
    r = 0

    gem_count = dict()
    for i in range(n):
        gem_count[i] = 0

    gem_set = set()

    def has_all_gems():
        return len(gem_set) == n

    def add_gem(item):
        gem_set.add(item)
        gem_count[item] += 1

    def remove_gem(item):
        gem_count[item] -= 1
        if gem_count[item] == 0:
            gem_set.remove(item)

    add_gem(0)

    while r < len(gems):

        if has_all_gems():
            if answer[1]-answer[0] > r-l:
                answer = [l+1, r+1]
                if r-l+1 == n:
                    break

        r += 1
        if r == len(gems):
            break

        add_gem(gems[r])

        while l <= r:
            gem = gems[l]
            remove_gem(gem)
            if gem_count[gem] > 0:
                l += 1
            else:
                add_gem(gem)
                break

    return answer