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

Link

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

My Solution (failed)

import heapq

def solution(gems):
    gems_uniq = list(set(gems))
    heap = []
    max_index = 0
    min_range = len(gems)
    for g in gems_uniq:
        index = gems.index(g)
        heapq.heappush(heap, (index, g))
        max_index = max(max_index, index)
        
    sol = [heap[0][0], max_index]
    min_range = max_index - heap[0][0]
    while heap:
        try:
            popped = heapq.heappop(heap)
            new_index = gems[popped[0] + 1:].index(popped[1]) + popped[0] + 1
            max_index = max(max_index, new_index)
            heapq.heappush(heap, (new_index, popped[1]))
            if max_index - heap[0][0] < min_range:
                sol = [heap[0][0], max_index]
                min_range = max_index - heap[0][0]
        except ValueError:
            break
        
    return [sol[0] + 1, sol[1] + 1]

heap 사용해서 짜봤지만 효율성 테스트는 대부분 fail이 떴다. list.index를 통해 찾는 시간이 너무 긴 것 같다.

투 포인터를 사용한 풀이

import heapq

def solution(gems):
    gems_uniq = list(set(gems))
    gems_map = {}
    for g in gems_uniq:
        gems_map[g] = 0
    
    r = 0
    l = 0
    gems_map[gems[0]] = 1
    gems_included = 1
    
    len_gems = len(gems)
    len_gems_uniq = len(gems_uniq)
    
    min_range = len(gems)
    sol = [0, len(gems) - 1]
    
    
    while l < len_gems and r < len_gems:
        if gems_included == len_gems_uniq:
            if r-l < min_range:
                min_range = r-l
                sol = [l, r]
            
            gems_map[gems[l]] -= 1
            if gems_map[gems[l]] == 0:
                gems_included -= 1
            l += 1
        else:
            r += 1
            if r >= len_gems:
                break
            gems_map[gems[r]] += 1
            if gems_map[gems[r]] == 1:
                gems_included += 1
    
    return [sol[0] + 1, sol[1] + 1]

map과 two pointer를 사용해서 풀면 효율성 테스트를 통과한다. two pointer 사용에 익숙해져야겠다...