[프로그래머스][투포인터] 보석 쇼핑

보석 쇼핑

 

• 첫 풀이 - 실패
  • remove(k)는 리스트에서 값을 찾아 제거하는 연산으로 O(N) 시간이 소요
  • min(result)와 max(result)도 각각 O(N)
  • 이 연산들이 루프 안에서 반복되면 전체 시간복잡도는 O(N^2)이 되어 시간 초과가 발생

def solution(gems):
    n=len(set(gems))
    answer = []
    
    gem_dict={}
    result=[]
    
    tmp=float('inf')
    for idx, gem in enumerate(gems):
        if gem in gem_dict:
            k=gem_dict[gem]
            result.remove(k)
            
        gem_dict[gem]=idx+1
        result.append(idx+1)
        
        if len(result)==n:
            if tmp>max(result)-min(result):
                tmp=max(result)-min(result)
                answer=[min(result),max(result)]
        
    return answer

 

• 두 번째 풀이
  • 최장연속부분수열 문제와 유사하게 떠올림

https://yygs321.tistory.com/436

[백준][최장연속부분수열][투포인터] 20922. 겹치는 건 싫어

 

• 슬라이딩 윈도우 + 투 포인터
  • left, right 두 개의 포인터를 사용해 구간 조절
  • right 로 윈도우를 확장하면서 보석을 추가하고, left 로 윈도우를 줄이면서 불필요한 보석을 제거
  • 윈도우 안에 모든 종류의 보석이 포함된 순간마다 최소 구간 길이를 갱신
    • → right와 left 포인터가 각자 최대 N번씩 이동하므로 총 O(N)

from collections import defaultdict

def solution(gems):
    n = len(set(gems))
    count = defaultdict(int)
    result = [0, len(gems)]
    l = 0

    for r in range(len(gems)):
        count[gems[r]] += 1

        # r이 늘어났을 때 l로 구간 줄여가면서 가능한 최단 구간 구하기
        while len(count) == n:
            if r - l < result[1] - result[0]:
                result = [l, r]

            count[gems[l]] -= 1
            if count[gems[l]] == 0:
                del count[gems[l]]
            l += 1

    return [result[0] + 1, result[1] + 1]