[Python] 백준 #19941 - 햄버거 분배

문제

---

19941번: 햄버거 분배

코드

---

My answer

import sys
input=sys.stdin.readline

n,k=map(int,input().split())
answer=0
seat=input()
for i in range(len(seat)):
    if(seat[i]=='P'):
        start=max(0,i-k)
        end=min(n,i+k+1)
        temp=seat[start:end]
        idx=temp.find('H')
        if(idx==-1):continue
        temp=temp[:idx]+'X'+temp[idx+1:]
        seat=seat[:start]+temp+seat[end:]
        answer+=1
print(answer)

Another answer

N, K = map(int, input().split())
location = list(input())
cnt = 0

for i in range(N):
    if location[i] == 'P':
        for j in range(max(i-K, 0), min(i+K+1, N)):
            if location[j] == 'H':
                location[j] = 0
                cnt += 1
                break

print(cnt)

풀이

---

이 문제도 그리디 문제로 해결방법은, 사람이 앉은 자리에서 +-K 만큼 범위에 있는 햄버거 중 가장 왼쪽 것을 먹는게 최선의 방법이다. 나는 +-K범위에서 햄버거를 찾은 뒤에 햄버거를 딴 걸로 바꿔줬다. 나는 바보같이, 시간을 줄이기위해 이중반복문이 아니라, find를 썼는데 find를 통해서 찾은 인덱스는 그 -k ~ k 범위의 인덱스이므로 더 복잡해진다. 따라서 그냥 이중 반복문을 이용해서 풀면 간단하다.