[백준] 19941 햄버거 분배 Node.js (Greedy)

Janet·2023년 6월 30일
0

Algorithm

목록 보기
240/314

문제

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

햄버거사람햄버거사람햄버거사람햄버거햄버거사람사람햄버거사람
123456789101112

위의 상태에서 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인 문자열로 주어진다.

출력

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

제한

  • 1 ≤ N ≤ 20,000
  • 1 ≤ K ≤ 10

예제 입력 1

20 1
HHPHPPHHPPHPPPHPHPHP

예제 출력 1

8

예제 입력 2

20 2
HHHHHPPPPPHPHPHPHHHP

예제 출력 2

7

문제풀이

💡 문제풀이 과정

  • 주어진 입력값을 반복문을 돌면서 현재 인덱스의 값이 ‘P’(사람)라면, 근처에 먹을 수 있는 ‘H’(햄버거)가 있는지 탐색한다.
  • 탐색의 범위의 시작은 현재 인덱스 - K부터 끝은 현재 인덱스 + K까지이다. 해당 탐색 범위 중에 햄버거가 있다면 방문(먹어치운 것)을 표시하기 위해 해당 인덱스의 값을 0으로 저장하고, 카운트를 증가시킨다.

✅ 답안

const filePath = process.platform == 'linux' ? '/dev/stdin' : './input.txt';
let [n, input] = require('fs').readFileSync(filePath).toString().trim().split('\n');
input = input.split('');
const [N, K] = n.split(' ').map(Number);

let result = 0;
for (let i = 0; i < N; i++) {
  if (input[i] == 'P') {
    const start = i - K;
    const end = i + K;
    for (let j = start; j <= end; j++) {
      if (input[j] == 'H') {
        input[j] = 0;
        result++;
        break;
      }
    }
  }
}
console.log(result);
profile
😸

0개의 댓글