Posts [알고리즘] 백준 19941 - 햄버거 분배
Post
Cancel

[알고리즘] 백준 19941 - 햄버거 분배


문제

19941 - 햄버거 분배


접근

그리디 알고리즘이다.

앞에서부터 차례대로 보면서 해결하면 된다.

나는 사람을 기준으로 해결했다.
우선 입력받은 값에서 햄버거와 사람을 나누어 담아준다.
인덱스를 기준으로 담아주면 된다.

그 후 앞에서부터 사람을 한명 선택하고, 왼쪽에서부터 햄버거를 확인한다.
햄버거를 하나 꺼내서 거리를 비교해보고 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)


This post is licensed under CC BY 4.0 by the author.

[알고리즘] 백준 18870 - 좌표 압축

[알고리즘] 백준 21735 - 눈덩이 굴리기