[프로그래머스] 보석 쇼핑 / 2020 카카오 인턴십 / python

투 포인터 방식으로 풀었다.

• 모든 보석을 가지고 있지 않다면 오른쪽 포인터를 한 칸 옮겨서 다음 보석의 카운트를 올려준다.
• 모든 보석을 가지고 있을 경우에는 왼쪽 포인터와 오른쪽 포인터의 거리 차이를 최소값으로 갱신한다.
• 갱신한 후에는 왼쪽 포인터를 한 칸 옮겨서 이제 범위 안에 해당하지 않는 보석의 카운트를 내려준다.
  • 이 때 보석의 카운트가 0이 되었을 경우 map에서 아예 없애주어야 한다.

헷갈려서 실수했던 부분이 있다.

• 왼쪽 포인터는 주어진 명령을 수행하고 포인터를 옮겨주었고, 오른쪽 포인터는 먼저 옮기고 나서 주어진 명령을 수행했다.
• 만약 오른쪽 포인터를 명령을 수행한 뒤에 옮기면 마지막 보석은 확인을 안하게 된다.
• 내가 지금 있는 곳에서 무언가를 없애고 옮겨가는 것과 새로운 곳에 가서 무언가를 추가하는 것. 어떻게 보면 당연한 건데 왜 헷갈려했는지 모르겠다 큽...

from collections import defaultdict


def solution(gems):
    result = [0, len(gems)]
    gem_kinds = len(set(gems))
    count_dict = defaultdict(int)
    count_dict[gems[0]] = 1

    left_idx, right_idx = 0, 0
    while right_idx < len(gems) and left_idx < len(gems):
        if len(count_dict) == gem_kinds:
            if result[1] - result[0] > right_idx - left_idx:
                result = [left_idx + 1, right_idx + 1]

            count_dict[gems[left_idx]] -= 1
            if count_dict[gems[left_idx]] == 0:
                del count_dict[gems[left_idx]]
            left_idx += 1

        else:
            right_idx += 1
            if right_idx == len(gems):
                break
            count_dict[gems[right_idx]] += 1

    return result