[Programmers][Python][67258][카카오 인턴] 보석 쇼핑

문제 링크

문제링크

첫 번째 풀이

투 포인터

기본적으로 투포인터는 부분합이 m이 되는 구간의 갯수를 찾는 문제입니다. left와 right는 0으로 시작합니다. s = [left,right]의 합입니다.

1. s == m 일때는 ans += 1, right += 1
2. s < m 일 때는 right += 1, s+= arr[right]
3. s > m 일 때는 s -= arr[left], left += 1

left<=right 조건을 만족하면서 증가하기 때문에 $O(n)+O(n) = O(n)$의 시간복잡도를 가집니다.

항공대 알고리즘 소학회 천수환님의 투 포인터 강의는 여기에서 확인하실 수 있습니다 ^^7

정답 코드

위에서 구간합을 구하는 과정을 보석의 갯수를 구하는 과정으로 바꾸어서 진행합니다.

counter를 사용해서 list안에 unique한 값의 갯수를 num_of_type으로 가져옵니다. left와 right 범위에 있는 unique value의 갯수는 right가 증가할 때 없는 값이 추가되면 늘어나고, left에서 유일한 값이 사라지면 줄어듭니다. ans = {‘RUBY’:0} 일 때 ‘RUBY’ in ans가 True를 리턴한다는 점에 유의해서 del을 해주어야 합니다.

ans에 처음 값을 넣어두고 left, right = 0,1로 시작하는 부분에서 구현력이 필요하다고 생각합니다. 깔끔하게 짜는게 쉽지 않네요! 생각해보니 cnt_of_type를 안쓰고 len(ans)를 사용해도 되겠습니다.

from collections import Counter 

def solution(gems):
    n = len(gems)
    num_of_type = len(Counter(gems).keys())
    ans = {gems[0]: 1}
    cnt_of_type = 1 # 찾은 unique value의 갯수 1로 시작
    left, right = 0, 0
    answer = [0, n - 1]
    while left <= right:
        # 정답 찾은 경우
        if cnt_of_type == num_of_type:
            # 더 짧은 답 갱신
            if right - left < answer[1] - answer[0]:
                answer = [left, right]
            # left += 1
            if ans[gems[left]] == 1:
                del (ans[gems[left]])
                cnt_of_type -= 1
            else:
                ans[gems[left]] -= 1
            left += 1

        # 부족한 경우
        elif cnt_of_type < num_of_type:
            # right += 1
            right += 1
            # 구간 확인
            if right == n:
                break
            if gems[right] in ans:
                ans[gems[right]] += 1
            else:
                ans[gems[right]] = 1
                cnt_of_type += 1
    return [answer[0]+1, answer[1]+1]

Success Notice: 수고하셨습니다.