[코딩인터뷰] 백준 3020번 개똥벌레

백준 3020번 개똥벌레

Prefix Sum 누적 합

import sys

N, H = map(int, input().split())
MAX = H + 2
top = [0] * MAX
bottom = [0] * MAX

for k in range(N):
    v = int(input())
    if k % 2 == 1:
        bottom[v] += 1
    else:
        top[v] += 1

total_top = [0] * MAX
total_bottom = [0] * MAX
for i in reversed(range(1, H+1)):
    total_bottom[i] = bottom[i] + total_bottom[i + 1]
    total_top[i] = top[i] + total_top[i + 1]

mini = 200001
count = 1
total = [0] * MAX
for m in range(1, H+1):
    total[m] = total_bottom[m] + total_top[H - m + 1]

    if total[m] == mini:
        count += 1
    elif total[m] < mini:
        count = 1
        mini = total[m]

print(f"{mini} {count}")

Binary Search 이분 탐색

import sys
import bisect

N, H = map(int, input().split())
top = []
bottom = []

for k in range(N):
    v = int(input())
    if k % 2 == 1:
        top.append(v)
    else:
        bottom.append(v)

top.sort()
bottom.sort()

mini = 200001
count = 1
for h in range(1, H+1):

    top_count = len(top) - bisect.bisect_left(top, h)
    bottom_count = len(bottom) - bisect.bisect_left(bottom, H + 1 - h)
    total_count = top_count + bottom_count

    if total_count == mini:
        count += 1
    elif total_count < mini:
        count = 1
        mini = total_count

print(f"{mini} {count}")