프로그래머스_python_보석 쇼핑

문제

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

코딩테스트 연습 - 보석 쇼핑

풀이

Two Pointer Algorithm

start pointer, end pointer 두 개를 설정해 조건에 따라 늘려간다. 간단하게 적어보면 아래와 같다.

 

1. start~end 구간 내 모든 보석이 포함되어 있다면

start pointer를 오른쪽으로 1칸 옮겨 구간을 좁힌다.

2. 아니라면

end pointer를  오른쪽으로 1칸 옮겨 구간을 넓힌다.

결과 > 시간초과

def solution(gems):
    jewelrySet = set(gems) # 중복 제거된 보석
    jewelryCount = len(jewelrySet) # 중복 제거된 보석의 수
    gemsCount = len(gems) # 진열된 모든 보석의 수
    answer = list()
    s, e = 0, jewelryCount
    
    while e<=gemsCount and s<=e: 
        windowSet = set(gems[s:e]) # 해당 구간에서 보석의 종류를 저장
        
        if (len(windowSet)==jewelryCount) : # 1. start~end 구간 내 모든 보석이 포함되어 있다면
            answer.append((s+1, e))
            if (s==e) : break
            s+=1
            
        else : e+=1 # 2. 아니라면
            
    return min(answer, key = lambda n : n[1]-n[0])

시간 초과

1. 해당 구간에서 보석의 종류를 미리 저장 (windowSet)

조건에 따라 앞뒤의 원소만 변경되기에 미리 보석의 종류를 저장해두고, 

s+1일때는 보석을 제거하고

e+1일때는 보석을 추가하여 연산을 줄일 수 있다.

 

* 보석을 제거하기 위해서는 해당 구간에서 각 보석의 개수를 저장하고 있어야 한다.

gems = ["a", "a", "b"], s=0, e=2, windowSet = {"a", "b"} 이고, s+=1 연산에 의해 보석을 제거한다. 

 

windowSet에서 "a"를 제거하면 windowSet = {"b"}

이때, gems[1:2] = ["a", "b"]이므로 windowSet는 값을 제대로 표현하지 못한다.

 

따라서, gems[1:2] 안에 "a"가 없을 때만 windowSet에서 "a"를 제거해야 한다.

2. 해당구간에서 보석의 개수를 미리 저장 (windowDict)

매번, 구간에 보석이 몇개 있는지 세는 것은 불리하다. 따라서 미리 보석의 개수를 저장해둔다.

s+1일때는 보석의 개수를 줄이고

e+1일때는 보석의 개수를 늘린다.

코드

from collections import defaultdict

def solution(gems):
    jewelrySet = set(gems) # 중복 제거된 보석
    jewelryCount = len(jewelrySet) # 중복 제거된 보석의 수
    gemsCount = len(gems) # 진열된 모든 보석의 수
    windowSet = set(gems[0:jewelryCount]) # 해당 구간에서 보석의 종류를 저장
    answer = list()
    
    s, e = 0, jewelryCount
    windowDict = defaultdict(int) # 해당 구간에서 각 보석의 개수를 저장
    for j in gems[s:e] : windowDict[j]+=1 
        
    while e<=gemsCount and s<=e: 
        if (len(windowSet)==jewelryCount) : # 1. start~end 구간 내 모든 보석이 포함되어 있다면
            answer.append((s+1, e))
            if (s==e) : break
                
            windowDict[gems[s]] -= 1 
            if windowDict[gems[s]]==0 : windowSet.remove(gems[s])
            s+=1
            
        else : # 2. 아니라면
            windowDict[gems[e%gemsCount]] += 1
            windowSet.add(gems[e%gemsCount])
            e+=1
            
    return min(answer, key = lambda n : n[1]-n[0])