[프로그래머스(파이썬/Python)] 보석 쇼핑(2020 카카오 개발자 인턴십)

https://programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

 

카카오의 효율성 문제를 풀면 눈물이 납니다.

 

이 문제를 풀 때도 1) O(N^2)으로 몇 가지 트릭을 넣은 풀이, 2) 이분 탐색으로 O(N*logN), 두 가지 방법을 시도해보았지만 모두 다 효율성 테스트를 통과하지 못했습니다...

 

사실, 이 문제에서 투 포인터를 써야겠다는 생각은 바로 들었지만 뭔가 계속 구현이 꼬이고 몇 가지 테스트 케이스가 틀리고를 반복하다보니 다른 방법으로 회피한 것 같은 느낌도 있었습니다.

 

그래도 어찌저찌 투 포인터(슬라이딩 윈도우)를 통해 정답 판정을 받은 뒤에는 약간 허무하기도 하고, 조금 더 연습을 해야겠다는 생각을 했습니다.

 

이 문제에서 투 포인터를 사용하는 전략은 간단합니다.

 

left, right 커서를 처음 지점에서 시작하고 right 커서를 오른쪽으로 이동시켜보면서(구간을 확장해보면서) 보석을 더 담아봅니다. 현재까지 보석의 종류의 개수가 모든 보석 종류의 개수와 같아졌을 때(문제의 조건을 만족했을 때), 왼쪽 커서를 오른쪽으로 이동시켜보면서 필요없는 보석이 담겨있는지 제거해주면 됩니다.

 

[풀이]

from collections import defaultdict
def solution(gems):
    answer = []
    # 전체 보석이 몇 개 있는지 확인
    gemsDict = defaultdict(int)
    totalGems = len(set(gems))
    length = len(gems)
    maxLength = 1000000

    left, right = 0, 0
    gemsDict[gems[left]] = 1
    count = 1

    # 투포인터를 구간 끝까지 탐색
    while left < length and right < length:

        # 모든 보석을 담았으면 왼쪽 포인터를 이동시켜본다.
        if count == totalGems:
            # 구간 길이가 최소이고, 인덱스가 작은 값을 기록
            # 왼쪽에서 오른쪽으로 포인터가 이동하므로 자동으로 인덱스는 작은 것이 최종적으로 기록된다.
            if right - left < maxLength:
                maxLength = right - left
                answer = [left + 1, right + 1]
            
            gemsDict[gems[left]] -= 1
            if gemsDict[gems[left]] == 0:
                count -= 1
            left += 1

        # 보석이 부족하면 오른쪽으로 구간을 확장해본다.
        else:
            right += 1
            if right < length:
                gemsDict[gems[right]] += 1
                if gemsDict[gems[right]] == 1:
                    count += 1

            # 구간에 끝까지 갔으면 더 이상 추가할 보석이 없음
            else:
                break
    return answer