[파이썬/Python] 백준 19941번: 햄버거 분배

📌 문제 : 백준 19941번

---

📌 문제 탐색하기

N : 식탁의 길이 $(1 ≤ N ≤ 20,000)$
K : 햄버거 선택할 수 있는 거리 $(1 ≤ K ≤ 10)$
P : 사람 위치
H : 햄버거 위치

사람과 햄버거 위치 정보로 햄버거를 먹을 수 있는 사람 수의 최댓값을 구하는 문제이다.

문제 풀이

⭐️ 햄버거 먹는 조건

• 자신의 위치에서 거리가 K 이하인 햄버거 먹기 가능
• 햄버거 1개만 먹기

길이 N인 사람과 햄버거 위치를 저장한 배열을 처음부터 돌면서
사람의 위치에 접근할 때마다 왼쪽, 오른쪽 각각 K만큼의 거리를 for문으로 탐색하고,
그 거리 내에 햄버거 위치가 있다면 탐색을 종료하고 그 위치에 먹었다라는 표시로 값을 변경한다.

❗️ K 거리 내 탐색 시 유의할 점

• 위치 저장한 리스트의 길이 = N
• K 거리를 탐색할 때 길이를 벗어나는 범위가 될 수 있기 때문에 고려해서 인덱스가 0 또는 N-1을 넘지 않도록 해야 한다.

그 후 전체 중에 값이 변경된 부분의 수를 센다면 햄버거를 먹은 사람의 수를 구할 수 있다.

K 거리 내 왼쪽 → 오른쪽으로 탐색을 진행한다.
범위 내에 햄버거가 있다면 그 위치 값을 변경하고, 그 변경한 횟수를 세서 출력으로 내보낸다.

가능한 시간복잡도

for문으로 N을 돌면서 K 거리 내 탐색 반복 → $O(N * K)$

최종 시간복잡도
$O(N * K)$로 최악의 경우 $O(20,000 * 10) = O(2*10^5)$ 0.5초내 연산이 가능할 것이다.

알고리즘 선택

왼쪽에서 오른쪽으로 탐색하면서 K 거리내 햄버거 탐색해 가장 왼쪽에 있는 햄버거 먹게 하기

---

📌 코드 설계하기

1. N, K 입력
2. 위치 입력
3. 먹은 사람 수 저장할 변수 정의
4. 사람 위치 찾고 K 거리내 왼쪽부터 오른쪽으로 햄버거 있는지 탐색
5. 결과 출력
   
   

---

📌 시도 회차 수정 사항

1회차

• 예제 2는 출력이 제대로 나오지만 예제 1의 출력이 1만큼 작은 7이 나왔다.
• 햄버거 있는지 탐색할 때 범위를 잘못 입력해서 1이 부족한 범위까지만 탐색하도록 구현했다.

# 사람 위치 찾기
for i in range(N):
    if locations[i] == 'P':
        # 햄버거 있는지 탐색
        for j in range(max(0, i - K), min(N, i + K)):	### 문제 위치
            if locations[j] == 'H':
                locations[j] = 0
                people += 1
                break

---

📌 정답 코드

import sys

input = sys.stdin.readline

# N, K 입력
N, K = map(int, input().split())

# 위치 입력
locations = list(input().rstrip())

# 먹은 사람 수 저장
people = 0

# 사람 위치 찾기
for i in range(N):
    if locations[i] == 'P':
        # 햄버거 있는지 탐색
        for j in range(max(0, i - K), min(N, i + K + 1)):
            if locations[j] == 'H':
                locations[j] = 0
                people += 1
                break

# 결과 출력
print(people)

• 결과