[Python] 보석 쇼핑

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

---

투 포인터 슬라이딩 윈도우로 풀어봤는데 런타임 에러가 뜬다 짧지만 효율성이 안 좋은듯

 

def solution(gems):
    answer = []
    jewels = set(gems)
    def expand(start, end):
        if start < end and end <= len(gems) and set(gems[start:end]) == jewels:
            answer.append([start+1, end])
    for i in range(len(gems)):
        expand(i,i+len(jewels))
        expand(i,i+len(jewels)+1)
 
    return sorted(answer, key=lambda x:x[0])[0]

 

카카오 해설대로 dict, 투포인터를 사용한 풀이

그냥 dict {}는 초기값 없이 += 1을 하게 될 경우에 오류가 나므로 value가 없을 경우 기본값을 넣어주는 defaultdict를 사용했다

 

import collections
 
 
def solution(gems):
    answer = [0,len(gems)]
    kind = len(set(gems))
    dic = collections.defaultdict(int)
    dic[gems[0]] += 1
    l, r = 0, 0
 
    while l < len(gems) and r < len(gems):
        if len(dic) < kind:
            r += 1
            if r == len(gems):
                break
            dic[gems[r]] += 1
        else:
            if r-l < answer[1] - answer[0]:
                answer = [l+1, r+1]
            else:
                dic[gems[l]] -= 1
                if dic[gems[l]] == 0:
                    del dic[gems[l]]
                l += 1
 
    return answer