[프로그래머스Lv.3] 보석쇼핑(파이썬)

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

프로그래머스

문제 접근

 

 
시작과 끝을 리턴??
완전탐색으로 모든 케이스를 다 구한다??
100% 시간초과가 발생한다.
 

힌트얻기 
Counter를 활용한 방법

하나하나씩 돌려가면서

Counter에 각 보석이 몇번 카운트 되었나 세어봅니다.

만약 Counter의 길이가 보석종류만큼 되었다면

모든 종류의 보석을 다 세었다는 뜻이 됩니다.

그럼 앞에서부터 하나씩 앞으로 오면서 케이스를 넣어줍니다.

1-7/2-7/3-7까지 가능하죠.

4-7부터는 Ruby가 생략되기 때문에 조건을 만족하지 못하고요.

이렇게 Counter를 적절하게 활용하는 게 팁이었습니다.

 

 

문제 코드

from collections import Counter


def solution(gems):
    answer = []
    count = Counter()

    now = 0
    num = len(set(gems))

    right = 0
    while right < len(gems):
        count[gems[right]] += 1

        right += 1
        while len(count) == num:
            count[gems[now]] -= 1
            if count[gems[now]] == 0:
                del count[gems[now]]

            now += 1
            answer.append([now, right])

    answer.sort(key=lambda x: (x[1] - x[0], x[0]))

    return answer[0]