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

19941번: 햄버거 분배

문제

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 K 이하인 햄버거를 먹을 수 있다.

햄버거	사람	햄버거	사람	햄버거	사람	햄버거	햄버거	사람	사람	햄버거	사람
1	2	3	4	5	6	7	8	9	10	11	12

위의 상태에서 K=1인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

K=2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 11번 위치에 있는 햄버거

식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 두 정수 N과 K가 있다. 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 N인 문자열로 주어진다.

출력

첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.

제한

 

---

접근 방법

• P 입장에서 K 만큼 떨어진 곳, K-1 만큼 떨어진 곳 … 을 검사하면서 먹을 수 있는 햄버거인지 판단
• 먹을 수 있는 햄버거이면 먹었다고 표시
• 순서대로 P 하나씩 검사

 

풀이

N, K = map(int, input().split())  # 식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K
PH_list = input()  # P와 H로 이루어진 문자열 입력받기
PH_list= list(PH_list) # 입력받은 문자열을 글자 하나씩 리스트에 넣음
cnt = 0

for i in range(N):
    if PH_list[i] == 'P':  # 리스트에서 P일 때만 탐색 시작
        for j in range(i - K, i + K + 1):  # K만큼 떨어진 곳들을 탐색
            if 0 <= j < N and PH_list[j] == 'H':
                PH_list[j] = "-"  # 햄버거를 먹었다면 H 자리를 -으로 바꿈
                cnt += 1
                break

print(cnt)

---

 

💡 Challenge

첫 번째 시도

N, K = map(int, input().split()) # 식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K

PH_list = input() # P와 H로 이루어진 문자열 입력받기
PH_list= list(PH_list) # 입력받은 문자열을 글자 하나씩 리스트에 넣음
cnt = 0

for i in range(N):
  if (PH_list[i] == 'P'): # 리스트에서 P일 때만 탐색 시작
    for j in reversed(range(K)): # K만큼 떨어진 곳들을 탐색 (먼 곳부터 먼저 탐색하도록 reversed)
      if (i-j-1 >= 0): # 인덱스 범위가 벗어나지 않을 때, 왼쪽 탐색
        if (PH_list[i-j-1] == 'H'): # 햄버거를 먹지 않은 상태인 'H'이라면 햄버거를 먹음
          PH_list[i-j-1] = "-" # 햄버거를 먹었다면 H 자리를 -으로 바꿈
          cnt += 1
          print(PH_list)
          break
      if(i+j+1 <= N-1): # 인덱스 범위가 벗어나지 않을 때, 오른쪽 탐색
        if (PH_list[i+j+1] == 'H'):
          PH_list[i+j+1] = "-" # 햄버거를 먹었다면 H 자리를 -으로 바꿈
          cnt += 1
          print(PH_list)
          
          break

print(cnt)

잘못된 이유

거리가 먼 곳부터 탐색하니까 못 먹고 버리는 H가 생김

-> 거리 순 말고 무조건 왼쪽부터 탐색한 후 오른쪽 탐색하도록 수정

두 번째 시도

N, K = map(int, input().split()) # 식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K

PH_list = input() # P와 H로 이루어진 문자열 입력받기
PH_list= list(PH_list) # 입력받은 문자열을 글자 하나씩 리스트에 넣음
cnt = 0

for i in range(N):
  if (PH_list[i] == 'P'): # 리스트에서 P일 때만 탐색 시작
    for j in reversed(range(K)): # K만큼 떨어진 곳들을 탐색 (먼 곳부터 먼저 탐색하도록 reversed)
      if (i-j-1 >= 0): # 인덱스 범위가 벗어나지 않을 때, 왼쪽 탐색
        if (PH_list[i-j-1] == 'H'): # 햄버거를 먹지 않은 상태인 'H'이라면 햄버거를 먹음
          PH_list[i-j-1] = "-" # 햄버거를 먹었다면 H 자리를 -으로 바꿈
          cnt += 1
          PH_list[i] = '+'
          break
      if (PH_list[i] != '+'):
        for j in reversed(range(K)): # K만큼 떨어진 곳들을 탐색 (먼 곳부터 먼저 탐색하도록 reversed)
          if (i+j+1 <= N-1): # 인덱스 범위가 벗어나지 않을 때, 오른쪽 탐색
            if (PH_list[i+j+1] == 'H'):
              PH_list[i+j+1] = "-" # 햄버거를 먹었다면 H 자리를 -으로 바꿈
              cnt += 1

              PH_list[i] = '+'
              break
print(cnt)

최종 제출한 코드

잘못 생각한 부분: 왼쪽 오른쪽으로 나눠서 구할 필요가 없다

i - K 부터 i + K + 1 을 탐색하면 K 만큼 떨어진 곳들을 한 번에 탐색할 수 있다.

N, K = map(int, input().split())  # 식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K
PH_list = input()  # P와 H로 이루어진 문자열 입력받기
PH_list= list(PH_list) # 입력받은 문자열을 글자 하나씩 리스트에 넣음
cnt = 0

for i in range(N):
    if PH_list[i] == 'P':  # 리스트에서 P일 때만 탐색 시작
        for j in range(i - K, i + K + 1):  # K만큼 떨어진 곳들을 탐색
            if 0 <= j < N and PH_list[j] == 'H':
                PH_list[j] = "-"  # 햄버거를 먹었다면 H 자리를 -으로 바꿈
                cnt += 1
                break

print(cnt)