[ 백준 - 19941 ] 햄버거 분배 ( 그리디 - 자바스크립트 )

문제

https://www.acmicpc.net/problem/19941

19941번: 햄버거 분배

 

문제를 제대로 이해 했는지?

 

한 사람이 테이블에 있는 햄버거를 집을 수 있는 범위를 줬을 때, 얼마나 많은 인원이 햄버거를 먹을 수 있는지 출력하시오.

 

풀이 방법에 대한 고찰

 

1) 최대한 많은 사람이 햄버거를 먹으려면?

 

 자신의 앞의 햄버거 중에서 가장 먼 것을 고를 때, 다른 사람이 햄버거를 잡을 수 있는 확률이 증가 

 

2) 범위만큼 순회를 ?

 

범위만큼 루프를 돌아도 될까? 라는 의문을 가졌는데 , 테이블의 최고 길이는 2만이고 집을 수 있는 범위도 최대 20이기 때문에 40만은 0.5초 안에 해결 할 수 있다.

 

 

3) 먹은 햄버거는 어떻게 구분?

 

처음에는 방문 처리를 할까? 생각을 했다가 불필요한 배열을 늘리는 것 같아서 다른 문자로 변경을 해줌으로써 이를 처리 할 수 있었다.

=> 먹은 햄버거는 사실상 없는거니까, 다른 사람의 기준에서 탐색 할 때 고를 경우를 아예 없어야한다.

 

 

전체 코드

function solution() {
  onTable = onTable.split("");
  let answer = 0;

  for (let i = 0; i < table_length; i++) {
    if (onTable[i] === "P") {
      // 탐색 범위를 위한 변수
      const start = i - 1 - diff;
      const end = i - 1 + diff;

      // [1] 왼쪽부터 시작하는 이유는 가장 맨 앞 쪽에서 부터 탐색 하기 위함.
      for (let j = start; j <= end; j++) {
        if (onTable[j] === "H") {
          // 햄버거 먹은 인원 증가.
          answer += 1;
          //[3] 먹었다는 처리를 위해 D(Done)로 문자를 바꿈
          onTable[j] = "D";
          // [2]햄버거를 만난 지점에서 탐색을 끝내야 여러 개의 햄버거를
          // 1명이 먹는 상황을 막음.
          break;
        }
      }
    }
  }
  console.log(answer);
}

const [table_length, diff] = [20, 2];

let onTable = "HHPHPPHHPPHPPPHPHPHP";

solution();