프로그래머스) 보석쇼핑

https://programmers.co.kr/learn/courses/30/lessons/67258?language=python3 

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

프로그래머스 문제는 항상 길다. 링크로 대체한다.

 

처음에는 투포인터가 의미없다고 생각해서 풀다가 계속해서 시간 초과가 떴다. 

결국, 답안을 보며 코드는 제외하고 이론만 습득한 후 구현을 했다.

투포인터를 이용해서 보석의 종류가 부족할 때는 end를 늘리고

보석의 종류가 다 모였다면 조건에 맞지 않을 때 까지 start를 늘려준다.

from collections import defaultdict as dfd
def solution(gems):
    gem_num = len(list(set(gems)))

    if gem_num == 1:
        return [1,1]
    check_gem = dfd(int)

    answer_len = len(gems)+1
    answer = []

    start = 0
    end = 0
    t1 = 1
    while end < len(gems):
        if t1 != gem_num:
            check_gem[gems[end]] +=1
            end += 1
        else:
            if answer_len > end - start:
                answer_len = end - start
                answer = [start + 1, end]

            check_gem[gems[start]] -= 1
            start += 1
        t1 = 0
        for i in check_gem:
            if check_gem[i] > 0:
                t1 += 1

    while t1 == gem_num:
        if answer_len > end - start:
            answer_len = end - start
            answer = [start + 1, end]
        check_gem[gems[start]] -= 1
        start += 1
        t1 = 0
        for i in check_gem:
            if check_gem[i] > 0:
                t1 += 1

    return answer

 이 코드는 시간 초과가 뜬다. t1변수에 값을 넣는 과정이 아주 비효율적인 것이 이유다.

check_gem 안에 값이 0이 되었을 때 해당 딕셔너리 원소를 삭제하고 t1은 check_gem의 길이를 반환하면 효율적인 코드로 변한다.

...
	check_gem[gems[start]] -= 1
    if check_gem[gems[start]] == 0:
        del check_gem[gems[start]]
    start += 1
t1 = len(check_gem)
...