[BOJ] 11941 햄버거 분배 (Python)

테이블에 햄버거와 사람이 놓여있고 일정 거리의 햄버거만 먹을 수 있다고 할 때, 햄버거를 먹을 수 있는 사람의 수를 구하는 문제이다. 그리디 알고리즘 영상을 보고 관련 문제를 풀어보았다.
예제 입력과 임의로 입력한 값들이 정답값으로 출력이 나와서 제출했더니 시간초과가 떴다.

시간초과 코드

import sys
N,K=map(int,sys.stdin.readline().split())
cnt=0
change=[0 for x in range(N)]
perli=list(map(str,sys.stdin.readline().strip()))
for i in range(len(perli)):
    if perli[i]=='P':
        if i-K>=0:
            perli[0:i-K]=change[0:i-K]
            perli[i]=0
            newli=perli[i-K:i+K+1]
            for x in range(len(newli)):
                if newli[x]=='H':
                    newli[x]=0
                    cnt+=1
                    perli[i-K:i+K+1]=newli
                    break
        else:
            perli[i]=0
            newli2=perli[:i+K+1]
            for y in range(len(newli2)):
                if newli2[y]=='H':
                    newli2[y]=0
                    cnt+=1
                    perli[:i+K+1]=newli2
                    break   
print(cnt)

min,max함수를 사용하면 간단하게 풀린다는 조언을 듣고 만든 코드이다. 위 코드보다 훨씬 간단하게 문제를 풀 수 있었다.

참고해서 만든 코드

import sys
N,K=map(int,sys.stdin.readline().split())
li=list(map(str,sys.stdin.readline().strip()))
cnt=0
for i in range(N):
    if li[i]=='P':
        minid=max(0,i-K)
        maxid=min(i+K,len(li)-1)
        for k in range(minid,maxid+1):
            if li[k]=='H':
                cnt+=1
                li[k]='0'
                break
print(cnt)

하지만 처음 짰던 코드로도 완성 시켜보고 싶어서 기존 코드에서 불필요한 부분을 제거하며 코드를 수정했다. 처음 코드에서는 입력받은 배열에서 더이상 참조하지 않을 요소의 값을 모두 변경해주었는데, 이번에는 탐색할 구간을 설정하고 조건에 맞는 요소만 값을 변경해 주었다.

시간초과 코드를 수정해서 성공한 코드

import sys
N,K=map(int,sys.stdin.readline().split())
cnt=0
perli=list(map(str,sys.stdin.readline().strip()))
for i in range(len(perli)):
    if perli[i]=='P':
        if i-K>=0:
            if i+K>=len(perli):
                for x in range(i-K,len(perli),1):
                    if perli[x]=='H':
                        perli[x]=0
                        cnt+=1
                        break
            else:
                for x in range(i-K,i+K+1):
                    if perli[x]=='H':
                        perli[x]=0
                        cnt+=1
                        break
        else:
            for y in range(0,i+K+1):
                if y>=len(perli):break
                elif perli[y]=='H':
                        perli[y]=0
                        cnt+=1
                        break  
print(cnt)