[프로그래머스] / [Level 3] / [Python] 보석 쇼핑

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

프로그래머스

---

2중 for문을 사용한다면 쉽게 해결이 가능하지만, 시간 초과를 출력한다.

결국 시간 복잡도가 O(n)인 방식을 사용해야하는데, 투포인터 알고리즘을 사용하여 해결을 시도하였다.

 

처음에는 특정 범위에서 필요한 보석 수의 갯수만 있으면 된다고 판단하여 len(set(gems[start:end])) 를 사용하였다.

하지만 매번 해당 범위를 slice하고 집합으로 처리하는 과정에서 많은 시간이 소요된다는 것을 파악하였고,

질문하기에서 힌트를 얻어 defaultdict을 사용하여 실시간으로 갯수를 업데이트 하도록 하였다.

 

시간 초과 풀이

def solution(gems):
    answer = []

    len_gems = len(gems)
    len_set_gems = len(set(gems))

    start = 0
    end = len_set_gems
    
    while True:
        if len(set(gems[start:end])) < len_set_gems:
            if end < len_gems:
                end += 1
            else:
                break
        else:
            start += 1
            if len(set(gems[start:end])) < len_set_gems:
                if answer == []:
                    answer = [start, end]
                else:
                    if answer[1] - answer[0] > end - start:
                        answer = [start, end]

    return answer

수정한 풀이

from collections import defaultdict

def solution(gems):
    answer = []

    len_gems = len(gems)
    len_set_gems = len(set(gems))

    dd = defaultdict(int)

    start = 0
    end = len_set_gems
    
    for i in range(len_set_gems):
        dd[gems[i]] += 1
        
    while True:
        if len(dd) < len_set_gems:
            if end < len_gems:
                end += 1
                dd[gems[end-1]] += 1
            else:
                break
        else:
            dd[gems[start]] -= 1
            if dd[gems[start]] == 0:
                del dd[gems[start]]
                
            start += 1

            if len(dd) < len_set_gems:
                if answer == []:
                    answer = [start, end]
                else:
                    if answer[1] - answer[0] > end - start:
                        answer = [start, end]

    return answer