[프로그래머스] 보석 쇼핑 (python)

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

---

 

투포인터를 사용하자. right 값을 하나씩 늘려가며 left을 줄여보자!

처음에 right를 먼저 줄인다음에 left를 줄이니 아래 테스트 케이스 불통이였다. (오답: [1, 4])

gems = ["DIA", "EM", "EM", "RUB", "DIA"] # 답 [3,5]

 

1. 현재가지고 있는 보석을 담는 gdict를 생성한다.
2. 보석 종류 수 gnum을 구한다.
3. left = right = 0 를 시작으로 right를 하나씩 늘리며 보석을 추가한다.
4. 보석종류를 다 갖췄을 때(len(gdict) == gnum) left에 있는 보석이 중복이라면 없애준다.
5. answer 최소값을 update해준다.

 

from collections import defaultdict


def solution(gems):
    gdict = defaultdict(int)
    gnum = len(set(gems))

    left = 0
    right = 0
    answer = [0, len(gems)]
    while right < len(gems):
        gdict[gems[right]] += 1
        right += 1

        if len(gdict) == gnum:
            while left < right:
                if gdict[gems[left]] <= 1:
                    break
                gdict[gems[left]] -= 1
                left += 1

            if answer[1]+1-answer[0] > right - left:
                answer = [left+1, right]

    return answer