백준 온라인 저지, 그리디 / 19941번: 햄버거분배 (파이썬 / , 백준 실버문제)

문제

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다.

햄버거	사람	햄버거	사람	햄버거	사람	햄버거	햄버거	사람	사람	햄버거	사람
1	2	3	4	5	6	7	8	9	10	11	12

위의 상태에서 $K = 1$인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

$K = 2$인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 11번 위치에 있는 햄버거

식탁의 길이 $N$, 햄버거를 선택할 수 있는 거리 $K$, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 두 정수 $N$과 $K$가 있다. 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 $N$인 문자열로 주어진다.

출력

첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.

제한

• $1 \le N \le 20,000$
• $1 \le K \le 10$

예제 입력 1

20 1
HHPHPPHHPPHPPPHPHPHP

예제 출력 1

8

예제 입력 2

20 2
HHHHHPPPPPHPHPHPHHHP

예제 출력 2

7

힌트

접근 방법

- 0. 햄버거와 사람에 대한 정보를 차례로 탐색한다.
- 1. 햄버거가 나올 경우 해당 위치를 중심으로 하는 minheapH에 저장한다.
- 2. 사람이 나올 경우에는 해당 위치를 중심으로 하는 minheapP에 저장한다.
- 3. minheapP를 기준으로 값을 하나씩 빼며, k개 이내에 위치한 minheapH에 저장된 햄버거를 하나씩 세고 빼주며 햄버거를 먹을 수 있는 사람의 수를 증가한다.
- 3-1. 단, 햄버거의 위치가 더 낮은데, 사람과의 거리가 k 이상이라면 minheapH에서 값을 빼주고, 사람의 위치가 더 낮은데 햄버거와의 거리가 k 이상이라면 minheapP에서 값을 빼준다.

코드

# https://www.acmicpc.net/problem/19941
# 0. 햄버거와 사람에 대한 정보를 차례로 탐색한다.
# 1. 햄버거가 나올 경우 해당 위치를 중심으로 하는 minheapH에 저장한다.
# 2. 사람이 나올 경우에는 해당 위치를 중심으로 하는 minheapP에 저장한다.
# 3. minheapP를 기준으로 값을 하나씩 빼며, k개 이내에 위치한 minheapH에 저장된 햄버거를 하나씩 세고 빼주며 햄버거를 먹을 수 있는 사람의 수를 증가한다.
# 3-1. 단, 햄버거의 위치가 더 낮은데, 사람과의 거리가 k 이상이라면 minheapH에서 값을 빼주고, 사람의 위치가 더 낮은데 햄버거와의 거리가 k 이상이라면 minheapP에서 값을 빼준다.
import heapq

n, k = map(int, input().split())
arr = input()
minheapH = []
minheapP = []
for i in range(n):
    if arr[i] == 'H':
        heapq.heappush(minheapH, i)
    else:
        heapq.heappush(minheapP, i)

count = 0
while minheapP:
    x = heapq.heappop(minheapP)
    while minheapH:
        if minheapH[0] - x > k:
            break
        y = heapq.heappop(minheapH)
        if abs(x - y) <= k:
            count += 1
            break
print(count)