[백준][Python] 15823 카드팩 구매하기 : 이분탐색과 실패함수 비교

 

1. 투포인터 후 큰 숫자부터 cnt 50점 통과

import sys
input = sys.stdin.readline
from collections import defaultdict

N, M = map(int, input().split())
cards = list(map(int, input().split()))
cards.append(cards[-1])

# 연속된 카드 묶기. 정확히 M개의 카드팩. 같은 종류 카드 두장되면 안됨.
# 카드팩의 최대 길이.
left = 0
pack_cnt = []
card_pack = defaultdict(int)
for right in range(N+1):
    card_pack[cards[right]] += 1
    if card_pack[cards[right]] > 1:
        pack_cnt.append(right-left)
    while card_pack[cards[right]] > 1:
        card_pack[cards[left]] -= 1
        left += 1

pack_cnt.sort(reverse=True)
for i in range(max(pack_cnt),1,-1):
    max_cnt = 0
    for cnt in pack_cnt:
        max_cnt += cnt//i
    if max_cnt >= M:
        print(i)
        exit()
else:
    print(1)

 

2. 이분탐색 후 슬라이딩 윈도우. 50점

import sys
input = sys.stdin.readline
from collections import defaultdict


def is_Possible(pack_size):
    visited = defaultdict(int)
    cnt = 0
    left = 0
    for right in range(N+1):
        visited[cards[right]] += 1
        while visited[cards[right]] > 1:
            visited[cards[left]] -= 1
            left += 1
        if right-left+1 == pack_size:
            cnt += 1
            while left != right:
                visited[cards[left]] -= 1
                left += 1
    if cnt >= M:
        return True
    return False



N, M = map(int, input().split())
cards = list(map(int, input().split()))
cards.append(cards[-1])
left = 1
right = N
answer = 0
while left <= right:
    mid = (left+right)//2
    if is_Possible(mid):
        left = mid + 1
        answer = mid
    else:
        right = mid - 1
print(answer)


def my_bisect(lo, hi):
    answer = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        cnt = count_m(mid)
        if cnt >= M:
            answer = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return answer

 

3. 이분탐색 후 실패함수로 점프 // 가면서 나왔던 숫자 index로 저장해놨다가 다시 그지점으로 돌아아가 그 다음부터 비교함.(실패함수 개념) 200점

 

# 길이가 m인 윈도우(팩) 수 // 슬라이딩 윈도우가 아니라 윈도우 실패함수.를 dict로 구현.
def count_m(mid):
    cnt = 0
    move = 0

    while mid + move <= N:
        # 같은 거 중복할때까지 전진
        visited = dict()
        for i in range(move, move + mid):
            # 중복시 다음 스타트 지점
            # 전에 나온놈 인덱스 저장하고 중복시 여기인덱스 바로 뒤로 점프해 다시탐색(실패함수.) 
            if cards[i] not in visited:
                visited[cards[i]] = i
            else:
                move = visited[cards[i]] + 1
                break
        # 반복문 후 else = 반복문 종료시 1회 실행
        else:
            cnt = cnt + 1
            move = move + mid

    return cnt


N, M = map(int, input().split())
cards = list(map(int, input().split()))

# 카드팩 최소, 최대 크기
lo = 1
hi = N//M
print(my_bisect(lo, hi))