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

문제풀이

1. 딕셔너리 자료형 c을 활용하여 보석의 종류 수를 셉니다. c[보석 종류 x] = i~j까지 있는 보석 중 보석 종류 x의 수

2. gems의 맨 앞 인덱스 j부터 보석을 체크합니다. (i는 0부터 시작합니다.)

2-1. c의 모든 value가 1 이상이 되어야 모든 보석 종류를 최소한 하나씩 사게 됩니다.

2-2. 2-1의 조건을 만족하기 시작하면 c[i번째 보석의 종류] > 1인 경우에는 i를 하나 증가시켜 줍니다. ( i번째 보석을 빼도 모든 종류의 보석을 살 수 있습니다.)

 

* 문제에서는 0이 아닌 1부터 시작하므로 i와 j는 1씩 더해서 계산해야합니다.

 

for 문이 한번 돌아가므로 시간 복잡도는 O(n)이 됩니다.

Python Code

def solution(gems):
    tmp = set(gems)
    # 각 보석이 몇 개 있는 지
    c = {}
    for t in tmp:
        c[t] = 0
    # 보석의 종류 수 
    check = 0
    # 보석의 전체 종류
    tot = len(tmp)
    i = 0
    answer = [0,len(gems)]
    for j, item in enumerate(gems):
        if c[item] == 0 : check += 1
        c[item] += 1
        while i < j and c[gems[i]] > 1 :
            c[gems[i]] -= 1
            i += 1
        if check == tot and j-i < answer[1] - answer[0]:
            answer = [i+1,j+1]
    
    return answer

Line 19 : 모든 보석을 포함하며 이전보다 구간 길이가 줄어든 경우 answer를 i와 j로 바꿔줍니다.

문제 링크

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