프로그래머스|보석 쇼핑

문제 설명

중복된 원소들이 존재할 수도 있는 배열에서 모든 원소들을 적어도 하나 이상 포함한 가장 짧은 구간을 찾는 문제입니다. 만약 가장 짧은 구간이 여러개일 경우 시작점이 가장 작은 구간을 구해야합니다.
문제 링크

작동 순서

1. 배열 안 원소들의 종류별로 개수를 셀 수 있도록 딕셔너리를 생성해 줍니다.
2. 시작 구간은 시작점과 종료점 모두 0으로 지정해 줍니다.
3. 시작점이 0이기 때문에, 딕셔너리에 배열의 첫 원소의 개수를 +1 해줍니다.
4. 반복문을 돌면서 시작점에 있는 원소가 딕셔너리에 2개 이상 저장되어 있는 경우 시작점을 뒤로 한 칸 밀어줍니다. 이때 딕셔너리에서 시작점 원소의 개수를 -1 해줍니다.
5. 만약 시작점에 있는 원소가 딕셔너리에 1개만 저장되어 있는 경우 종료점을 뒤로 한 칸 밀어주고 딕셔너리에서 그 배열의 원소 개수를 +1 해주고 모든 원소를 모으기 위해 필요한 원소의 개수를 -1 해줍니다.
6. 만약 모든 원소가 모인 경우 기존의 구간(초기 구간은 배열의 시작부터 끝입니다-배열의 시작부터 끝을 모두 구간으로 할 경우 무조건 모든 원소가 존재합니다)과 비교하며 더 짧은 구간을 저장합니다. 이때 배열의 인덱스는 0으로 시작하기 때문에 구간의 시작점과 종료점에 1을 더 한 값을 저장해주어야 합니다.
7. 반복문을 돌다가 탐색 범위가 배열의 길이를 넘어가면 반복문을 종료하고 저장되어 있는 구간을 답으로 저장합니다.

소스코드

def solution(gems):
    answer = [1, len(gems)]

    inven = {gem: 0 for gem in set(gems)}
    start, end = 0, 0
    inven[gems[0]] += 1
    need_type = len(inven) - 1

    while end < len(gems):
        if need_type == 0 and answer[1] - answer[0] > end - start:
            answer = start + 1, end + 1

        if inven[gems[start]] > 1:
            inven[gems[start]] -= 1
            start += 1
        else:
            end += 1
            if end < len(gems):
                inven[gems[end]] += 1
                if inven[gems[end]] == 1:
                    need_type -= 1
    return answer

여담

23-24 유럽대항전 끝...