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

출처: 프로그래머스

문제

풀이

Counter를 이용하여 구현해주었습니다.

cnt_gems에 gems의 Counter를 저장해줍니다.

start와 end는 각각 포함하는 보석의 시작 index와 끝 index를 의미합니다.

구간을 최소화하기 위해서는, 조건을 충족하면서 start는 최대화, end는 최소화되야합니다.

우선, 모든 보석을 포함해주는 상태에서 e 위치에 있는 보석의 개수가 1보다 크다면 e를 점점 줄여줍니다. e를 줄이면서 cnt_gems의 e 위치에 있는 보석의 수도 줄여주어야 합니다. 적어도 하나는 포함해야 하기 때문에 e 위치에 있는 보석의 수가 1이라면 end에 e를 저장해주고 break 해줍니다.

이제 end를 늘려가며 각 end값마다 start의 최대값을 구해줍니다. 구하는 방식은 비슷합니다. start위치에 있는 보석의 수가 1보다 크다면 해당 보석의 수를 1 감소시키고 start를 늘려줍니다. start위치에 있는 보석의 수가 1이라면 break하고 해당 구간을 answer에 추가해줍니다.

end를 늘려가며 비교해주고 있기 때문에 다음 end index가 존재한다면 해당 위치에 있는 보석의 수를 늘려주어야합니다.

마지막에는 answer를 범위의 길이가 작은 순서로, 범위의 길이가 같다면 start가 작은 순서로 정렬해준 뒤 첫 번째 원소를 return 해줍니다.

코드

from collections import Counter
def solution(gems):
    answer = []
    cnt_gems = Counter(gems)
    start, end = 0, len(gems)
    # start가 0인 상태에서 가질 수 있는 end의 최소값 구하기
    for e in range(len(gems)-1, -1, -1):
        if cnt_gems[gems[e]] == 1:
            end = e
            break
        cnt_gems[gems[e]] -= 1
    # end를 늘려주며 각 end마다 start의 최대값을 구하기
    for e in range(end, len(gems)):
        while start < e:
            if start < len(gems) and cnt_gems[gems[start]] == 1:
                break
            cnt_gems[gems[start]] -= 1
            start += 1
        answer.append([start+1, e+1])
        if e+1 < len(gems):
            cnt_gems[gems[e+1]] += 1
    return sorted(answer, key=lambda x:(x[1]-x[0], x[0]))[0]