문제
접근
그리디 알고리즘이다.
앞에서부터 차례대로 보면서 해결하면 된다.
나는 사람을 기준으로 해결했다.
우선 입력받은 값에서 햄버거와 사람을 나누어 담아준다.
인덱스를 기준으로 담아주면 된다.
그 후 앞에서부터 사람을 한명 선택하고, 왼쪽에서부터 햄버거를 확인한다.
햄버거를 하나 꺼내서 거리를 비교해보고 k보다 멀면 버리고, 작으면 먹는다.
이 때 주의할 점은 햄버거의 위치가 사람보다 뒤에 갈 경우이다.
햄버거가 앞에 있다면 현재 사람이 먹지 못하면 그보다 뒤에 있는 사람도 당연히 먹지 못하므로, 버려도 상관없다.
하지만 햄버거가 사람보다 뒤에 있는 경우는 뒤의 사람이 먹을 수 있을지도 모른다.
따라서 버리지 않고, 덱의 가장 앞에 다시 삽입해준다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import deque
n, k = map(int, input().split())
arr = input().split()[0]
burger = deque()
person = deque()
for idx, item in enumerate(arr):
if item == 'P':
person.append(idx)
elif item == 'H':
burger.append(idx)
ans = 0
while person:
personLoc = person.popleft()
while burger:
burgerLoc = burger.popleft()
if abs(burgerLoc - personLoc) <= k:
ans += 1
break
if burgerLoc > personLoc:
burger.appendleft(burgerLoc)
break
print(ans)