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

 문제

 

programmers.co.kr/learn/courses/30/lessons/67258

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

 

 

 

 문제 상황

 

- 전체 리스트의 모든 요소를 최소한 1개씩은 포함하는 최소 길이의 부분 수열 찾기

 

 

 

 해결 전략

 

- 처음에는 LIS와 같은 유형의 문제인줄 알고 접근하였으나 left, right 두가지 인덱스를 활용하는 문제였다. 

 

- 모든 요소를 포함할 때까지 right 요소를 움직이며 모든 요소가 되었을 때에는 왼쪽 리스트를 움직이며 조건에 맞는 상황 중 최소를 찾는다.

 

 

 

 코드

 

def solution(gems):
    cache = dict()
    # for i in range(len(gems)):
    #     if gems[i] not in cache:
    #         cache[gems[i]] = 0
    left, right = 0, 0
    cache[gems[left]] = 1
    min_idx = (0,len(gems)-1)
    n = len(list(set(gems)))
    while True:
        # 만약 r이나 l이 구간을 벗어나면 종료
        if left >= len(gems) or right >= len(gems):
            break
        # 만약 이 구간에서 보석이 전부 존재한다면
        # if 0 not in cache.values():
        if n == len(cache):
            # 길이가 최소인지 판단하고 최소라면 현재 길이를 저장해준다.
            if min_idx[1]-min_idx[0] > right - left:
                min_idx = (left, right)
            cache[gems[left]] -= 1
            if cache[gems[left]] == 0 :
                del cache[gems[left]]
            left += 1
        # 보석의 종류가 부족하다면
        else:
            right += 1
            # right에 있는 보석의 count를 1 늘려준다.
            if right < len(gems) : 
                cache[gems[right]] = cache.get(gems[right], 0) + 1
    return (min_idx[0]+1, min_idx[1]+1)

 

 해설

 

- dictionary를 생성하여 gems 의 상태를 표시한다. 처음에 몇개인지 확인하고, 그 개수와 같아지는 상황을 만든다. 처음에는 둘다 인덱스 0에서 출발하여 오른쪽으로 움직이는데 만약 gems의 보석 종류보다 적으면 right을 움직여 보석의 종류를 확보하고 모든게 완성 되었을 땐 left를 줄이며 길이를 최소화 해본다. 길이가 최소일 때 인덱스를 갱신해주고 left가 왼쪽으로 가다보면 다시 보석이 부족해지는 상황이오고 그럼 다시 right을 움직여준다.

 

 새로 학습한 것 & 실수 

 

- 처음에는 dict의 요소를 0으로 초기화해주고 0인 요소가 있는지 values를 통해 확인하였다. 이 연산은 values 자체가 N의 시간이 걸리고 이를 다시 in 을 이용해 N번 연산하므로 속도 이슈에 걸린다. 하지만 len(dict) 를 이용하면 N에 연산이 가능하므로 속도 이슈가 없다. 아예 없애는 것을 고려하자.