2020 카카오 인턴십 - 보석 쇼핑 (Level 3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import defaultdict

def solution(gems):
    nu = len(set(gems))
    answers = []

    # Sliding window
    cnt = defaultdict(int)
    i_start, i_end = 0, 0
    while True:
        if len(cnt) < nu:
            if i_end == len(gems):
                break
            cnt[gems[i_end]] += 1
            i_end += 1
        else:
            cnt[gems[i_start]] -= 1
            if cnt[gems[i_start]] == 0:
                del cnt[gems[i_start]]
            i_start += 1
            answers.append([i_start, i_end])

    return min(answers, key=lambda answer: (answer[1]-answer[0], answer[0]))