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

난이도 : LV3

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/67258

문제해결 아이디어

• 보석 배열의 길이가 100,000 이하였기 때문에 nlog(n)으로 풀어야 된다고 생각했다.
• 배열의 처음부터 끝까지 구간을 나누어 탐색하는 투포인터가 적합하다고 생각되었다.
• 이때 딕셔너리를 통해 딕셔너리[보석] = 개수 를 통해 구간 별로 갖고있는 보석의 개수를 저장했다.

소스코드

def solution(gems):
    jew = {gems[0]:1} 
    start_idx, end_idx = 0,0
    kind = list(set(gems)) #보석의 종류
    _len = len(gems)
    ans = [1, _len]
    while start_idx < _len and end_idx < _len:
        if len(jew) == len(kind): #구간의 보석의 종류와 전체 종류가 동일하다면
            if ans[1] - ans[0] > end_idx - start_idx: #진열대 길이 비교
                ans[0] = start_idx + 1
                ans[1] = end_idx + 1
            
            if jew[gems[start_idx]] > 1: 
                jew[gems[start_idx]] -= 1
            else:
                jew.pop(gems[start_idx])
            start_idx += 1 #시작점을 다시 끌어올림
        else:
            end_idx += 1 #끝점을 뒤로 늘림
            if end_idx == _len:
                break
            if gems[end_idx] in jew:
                jew[gems[end_idx]] += 1
            else:
                jew[gems[end_idx]] = 1
    
    
    return ans