백준 19941 햄버거 분배 Python

🐸 문제 정보

19941번: 햄버거 분배

 

🤖 알고리즘

그리디

 

⏱️ 풀이 시간

17.29m

 

📝 풀이

투포인터로 풀어야하는 문제인가..?하고 5분정도 삽질하다가 그리디로 해결했다.

생각보다 시간초과도 안나고 단순하게 풀 수 있는 문제였다.

 

1. 왼쪽부터 오른쪽으로 탐색
   • 이때 테이블 리스트에는 왼쪽과 오른쪽에 k개 만큼 추가 요소가 있어야 함
     • 2번의 탐색 단계에서 의미 없는 조건문이 필요하지 않도록
2. 현재 인덱스에 'P'가 나온 경우 주변 검색
   • 현재 인덱스부터 좌k 우k 에 'H'가 있다면, 그 'H'는 '-'로 바꿔서 다시 먹을 수 없게 함

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, k = list(map(int, input().rstrip().split()))
table = ['-'] * k + list(input().rstrip()) + ['-'] * k
res = 0

for i in range(k, n + k):
    if table[i] == 'P':
        for j in range(i-k, i+k+1):
            if table[j] == 'H':
                table[j] = '-'
                res += 1
                break

print(res)