백준 19941 - 햄버거 분배 (파이썬)

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

풀이

그리디 알고리즘을 활용하여 P(사람)가 H(햄버거)를 최대한 많이 먹을 수 있도록 하는 문제이다.

1. 각 사람은 자신의 위치에서 왼쪽, 오른쪽 K칸 이내에 있는 햄버거를 먹을 수 있다.
2. 같은 햄버거를 여러명이 먹을 수 는 없다.
3. 최대 몇 명이 햄버거를 먹을 수 있는지 구해라.

햄버거 위치를 우선순위 큐에 저장한다.

1. 문자열을 한번 순회하며 H의 위치를 pq에 저장한다.
2. 큐를 사용하면 햄머거를 오름차순으로 관리 할 수 있다.

사람이 등장하면 가장 가까운 햄버거를 찾는다.

1. P가 나오면 큐에서 H를 하나씩 꺼내서 사람이 먹을 수 있는 범위내에 있는지 확인한다.
2. 먹을 수 있으면 count += 1을 증가시키고, 다음 P로 넘어간다.
3. 만약 현재 H가 P의 범위를 벗어나면, 다음 H를 확인한다.

시간 복잡도 분석

1. 문자열을 한번 순회하면서 H를 큐에 넣음 → O(N)
2. P를 순회하면서 햄버거와 매칭 → O(N)

즉, 총 시간 복잡도는 O(N)으로 매우 효율적

코드

# 백준 19941 - 햄버거 분배
# 분류 : 그리디

from queue import PriorityQueue

N, K = map(int, input().split())
S = input()

pq = PriorityQueue()
for i in range(N) :
    if S[i] == "H" :
        pq.put(i)

count = 0
for i in range(N) :
    if S[i] == "P" :
        while pq.qsize() > 0 :
            x = pq.get()

            if abs(x - i) <= K :
                count += 1
                break

            if x < i :
                continue
            else :
                pq.put(x)
                break

print(count)