[Python] 19941번 햄버거 분배

✏️ 문제

 

문제 파악

일단 'H'를 기준, 경우의 수를 3가지로 나눴다.

1. H의 위치가 K보다 작을 경우: H를 기준으로 좌로 K만큼 비교할 때 배열 범위를 벗어난다.
2. H의 위치가 K보다 크고 N-K보다 작을 경우: H를 기준으로 좌우로 K만큼 비교할 수 있다.
3. H의 위치가 N-K 크거나 같을 경우: H를 기준으로 우로 K만큼 비교할 때 배열 범위를 벗어난다.

이때  i-k가 0보다 작으면, i+k가 n보다 크면 배열 범위를 벗어나므로 처리를 해주어야 한다!

 

알고리즘

• 그리디 알고리즘

 

 

코드

n, k = map(int, input().split())
ary = list(map(str, input()))
start = 0
end = 0

for i in range(len(ary)):
  if ary[i] == 'H': 
    if i < k:
      end = i+k+1
    elif n - k <= i:
      start = i-k
      end = n
    else:
      start = i-k
      end = i+k+1

    if start < 0:
      start = 0
    if end > n:
      end = n
      
    for j in range(start, end):
      if ary[j] == 'P':
        ary[i] = ''
        ary[j] = ''
        break
  
print(int(ary.count('') / 2))