(Python) 프로그래머스 - [카카오 인턴] 보석 쇼핑

05 Mar 2022 in Algorithm on Programmers, Level3

[문제 링크]

풀이

def solution(gems):
    jewel_cnt = len(set(gems))
    dp = []
    end = -1
    tmp = dict()
    length = len(gems) - 1

    for start in range(length):
        while end < length or len(tmp) == jewel_cnt:
            if len(tmp) == jewel_cnt:
                dp.append((start, end, end - start))
                if tmp[gems[start]] == 1:
                    tmp.pop(gems[start])
                else:
                    tmp[gems[start]] -= 1
                break
            else:
                end += 1
                if gems[end] not in tmp:
                    tmp[gems[end]] = 1
                else:
                    tmp[gems[end]] += 1

    dp.sort(key=lambda x: (x[2], x[0]))

    return [dp[0][0] + 1, dp[0][1] + 1]