[Python/파이썬] 백준 15823번 카드 팩 구매하기

https://www.acmicpc.net/problem/15823

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(map(int, input().split()))


def chk(num):   # Two Pointer
    pack = set()
    l, r = 0, 0
    cnt = 0
    while r < n:
        if arr[r] not in pack:
            pack.add(arr[r])
            r += 1
        else:
            while arr[l] != arr[r]:
                l += 1
            l += 1
            r = l
            pack = set()
        if len(pack) == num:
            cnt += 1
            if cnt == m:
                return True
            pack = set()
    return False


def bs():   # Parametric Search
    s, e = 1, n
    ans = 0
    while s <= e:
        mid = (s+e)//2
        if chk(mid):
            s = mid+1
            ans = mid
        else:
            e = mid-1
    return ans


print(bs())

 

50점만 받을 수 있는 코드이다.

Parametric Search과 Two Pointer 알고리즘을 사용했는데, Parametric Search에서 조건을 검사할 때 Two Pointer를 사용한다.

 

bs() : Parametric Search

하나의 카드 팩을 구성할 수 있는 최대 카드 수를 Parametric Search로 찾는다. 조건은 chk() 함수를 이용하여 판단한다.

 

chk() : Two Pointer

하나의 카드 팩에 num개의 카드가 들어간다고 할 때 m개의 카드팩을 만들 수 있는지 여부를 리턴한다. 

l과 r이 가리키는 두 카드와 그 사이의 카드들이 하나의 팩을 구성할  수 있는지 검사하기 위해 pack이라는 집합을 이용한다. r을 오른쪽으로 한 칸씩 옮겨가며 만약 arr[r]이 아직 pack에 없는 수라면 같은 팩에 들어갈 수 있으므로 pack에 arr[r]을 추가하고 r++해주고, 만약 있는 수라면 같은 팩에 들어갈 수 없으므로 포인터 l을 중복되었던 수 다음 위치로 옮긴 후 r도 똑같은 위치로 옮겨서 다시 num개의 카드를 가진 팩을 찾는다.