백준 온라인 저지의 19941번 문제인 “햄버거 분배”를 풀다가 IndexError로 인해 런타임 에러가 발생했습니다. 투 포인터를 사용하여 문제를 해결하려 했는데, 인덱스를 증가시키는 과정에서 리스트의 범위를 벗어나 오류가 났습니다.
문제 설명
- 입력: 테이블의 길이
N과 사람(P)이 햄버거(H)를 선택할 수 있는 최대 거리K가 주어집니다. 이어서 테이블의 상태가 문자열로 주어집니다. - 목표: 각 사람은 자신을 중심으로
K만큼 왼쪽과 오른쪽에 있는 햄버거 중 하나를 먹을 수 있습니다. 각 햄버거는 한 번만 먹힐 수 있습니다. 최대 몇 명의 사람이 햄버거를 먹을 수 있는지를 구하는 것입니다.
초기 코
Python
# https://www.acmicpc.net/problem/19941
from sys import stdin
N,K = map(int,stdin.readline().split())
table = " ".join(stdin.readline()).split()
count = 0
eated = [False] * N
start = 0
end = K - 1
for i in range(N) :
if i < N - K:
end +=1
if i > K :
start+=1
if table[i] == "P" :
for j in range(start,end+1) :
if table[j] == "H" and not(eated[j]) :
count +=1
eated[j] = True
break
# print(eated)
print(count)- 생각: 투포인터를 사용해서 문제를 해결하려고 생각했습니다.
- 문제점:
start와end를 증가시키는 과정에서 테이블의 인덱스 범위를 벗어나IndexError가 발생했습니다. - 이유: 리스트의 인덱스는 0부터
N-1까지인데,start나end가 이 범위를 넘어설 수 있도록 코드를 작성하여 오류가 났습니다.
Python
# https://www.acmicpc.net/problem/19941
from sys import stdin
N,K = map(int,stdin.readline().split())
table = " ".join(stdin.readline()).split()
count = 0
eated = [False] * N
start = 0
end = K - 1
for i in range(N) :
if table[i] == "P" :
start = max(0, i - K)
end = min(N - 1, i + K)
for j in range(start,end+1) :
if table[j] == "H" and not(eated[j]) :
count +=1
eated[j] = True
break
# print(eated)
print(count)해결 방법
인덱스의 상한과 하한을 조정하기 위해 max()와 min() 함수를 사용하여 인덱스가 리스트의 범위를 벗어나지 않도록 수정했습니다.
최적화
Python
N, K = map(int, input().split())
HP = input()
ans = 0 # 먹을 수 있는 사람의 수
h = 0 # 햄버거를 가리키는 인덱스
for i, p in enumerate(HP):
if p != 'P':
continue # 사람이 아닐 경우 건너뜀
while h < N and (HP[h] != 'H' or h < i - K):
h += 1 # 햄버거가 아니거나 사람의 범위를 벗어난 햄버거는 넘어감
if h == N:
break # 햄버거가 더 이상 없으면 중단
if i - K <= h <= i + K: # 햄버거가 사람과 범위 내에 있으면
h += 1 # 해당 햄버거는 먹힘
ans += 1 # 사람이 햄버거를 먹을 수 있음
print(ans)
while문에서는 현재 사람이 탐색할 수 있는 거리 내에 있는 햄버거를 찾습니다. 만약 사람이 탐색할 수 있는 범위에 햄버거가 있다면 그 햄버거를 먹습니다. 이때, 찾은 햄버거가 사람의 탐색 범위에 포함되지 않는다면if문에 의해 해당 사람은 그 햄버거를 먹을 수 없으므로, 스킵하고 다음 햄버거를 찾을 때까지 진행됩니다. 이 과정에서 탐색 범위를 제한함으로써 최적화가 이루어집니다.
인덱스의 상한과 하한을 설정할 때 max()와 min() 함수를 사용하면 코드를 간결하고 안전하게 작성해야겠다.