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

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

 

이 문제를 보고 풀 수 있는 2.5 가지 아이디어가 떠올랐고, 제일 쉬운 것부터 시도해보았습니다.

 

1. 각 보석이 무조건 1번은 들어가야하기 때문에 보석명을 딕셔너리 키로 쓰고 여기서 하나씩 가져오자 (product 사용)

2. 슬라이딩 윈도우로 투포인터 방식으로 구간 내 보석을 확인하기

 

from itertools import product

def solution(gems):
    answer = []
    gem_list = {}
    
    for idx, gem in enumerate(gems):
        if gem in gem_list:
            gem_list[gem].append(idx)
        else:
            gem_list[gem] = [idx]
    
    candidate = list(product(*gem_list.values()))
    
    start = 1
    end = len(gems)
    for combi in candidate:
        combi = list(combi)
        combi.sort()
        if combi[-1] - combi[0] < end-start:
            start = combi[0] +1
            end = combi[-1] + 1
    answer = [start, end]
    return answer

 

위는 효율성 측면에서 시간포과가 나느 코드입니다. sort() 연산 자체가 O(n)이기 때문에 해당 코드는 꼼짝없이 시간초과가 됩니다.

혹시나 for combi... 부분을 min(), max()함수를 이용한 풀이도 마찬가지 입니다. (직접 해봄)

 

def solution(gems):
    answer = []
    count = len(set(gems))
    
    start = 0
    end = 0
    min_length = len(gems)
    gem_count = dict()
    
    for i in range(len(gems)):
        if gems[i] in gem_count: 
            gem_count[gems[i]] += 1
        else: gem_count[gems[i]] = 1
        end = i
        # print(gem_count)
        while len(gem_count.keys()) == count:
            if min_length > (end -start+1):
                answer = [start +1, end+1]
                min_length = end-start+1
                
            gem_count[gems[start]] -= 1
            if gem_count[gems[start]] == 0:
                del gem_count[gems[start]]
            
            start += 1
    
    if not answer:
        answer = [1, len(gems)]
    return answer

 

그렇다면 어떻게 해야하는지 정답 코드에서 확인해봅시다.

일단 start, end를 슬라이딩 윈도우 방식으로 검사하는 기본 아이디어는 맞습니다. 다만, 제가 고민된 지점은 어떤 경우에 start를 올려주어야 하냐는 것입니다. 바로 start를 한 칸씩 올려보면서 여전히 모든 gems를 쇼핑 리스트(여기선 gem_count)로 갖고 있으면 됩니다.

만약 start를 올렸는데 보석의 수가 0이면 거기서 스탑하고 end 탐색으로 다시 돌아갑니다.

 

또 제가 실수했던 부분이 두 가지가 있는데

첫번째는 start는 괜찮지만 와 end는 보다 싶이 for문의 인덱스이기 때문에 함수가 종료되면 무조건 len(gems)-1의 숫자를 갖습니다. 그렇기 때문에 while 문 내에서 조건이 충족할 때(min_length를 줄일 수 있을 때) 바로 업데이트 해주어야 합니다.

두 번째는 정답이 gems 함수 전체일 때 입니다. 이 경우엔 어떤 상황에도 start를 상승시키지 않기 때문에 answer가 여전히 빈 리스트로 남게 됩니다. 따라서 retrun 전에 answer를 한번 더 검사해주어야 합니다.