https://www.acmicpc.net/problem/19941
19941번: 햄버거 분배
기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사
www.acmicpc.net
from collections import deque
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = input()
arr = list(a.strip())
stack = []
pq = deque()
hq = deque()
cnt = 0
for i in range(len(arr)):
if arr[i] == 'H':
# 햄버거면
is_done = False
while pq:
# 사람 큐를 확인해서
idx = pq.popleft()
if i - idx <= k:
# 거리가 되면
cnt += 1
is_done = True
# cnt + 1
break
if is_done == False:
# 거리가 안되면 hq에 append
hq.append(i)
else:
is_done = False
while hq:
# hq 큐를 돌면서
idx = hq.popleft()
if i - idx <= k:
# 거리가 되면
cnt += 1
is_done = True
break
if is_done == False:
# 거리가 안되면 append
hq.append(i)
print(cnt)
처음 제출한 코드이다.
큐를 먼저 생각해 햄버거 큐, 사람 큐를 선언해,
반복문을 돌며 햄버거 일때 사람큐를 확인하며 거리가 되는 사람이 먹는다.
반대로 사람을때 햄버거 큐를 돌며 거리가 되면 먹는다.
그러나 실패했다.
생각한건 맞는데 도무지 테스트케이스가 부족해서 풀 수가 없었다.
결국 다른 방법을 떠올렸다.
n, k = map(int, input().split())
a = input()
arr = list(a.strip())
cnt = 0
for i in range(len(arr)):
if arr[i] == 'P':
for i in range(max(i - k, 0), min(i + k+1, n)):
#거리를 확인한다. (0과 현재위치 - 거리)의 최대값과 (현재위치 + 거리+1, n)의 최소값의 범위를 돌며 햄버거를 확인한다.
if arr[i] == 'H':
arr[i] = 'z'
#햄버거가 있으면 먹는다
cnt += 1
break
print(cnt)뭔가 더 깔끔해진거 같다.
너무 어렵게 생각한 문제같다.