백준 - 국회의원 선거(1417번) [JS]

백준 - 국회의원 선거(1417번)

이 문제는 결국 반복하며 최댓값을 찾는 문제이다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. 국회의원 후보의 수를 N으로 받는다.
2. 다솜이의 득표 수를 dasom으로 받고, 나머지 득표 수를 vote 배열로 저장한다.
3. counter 변수를 0으로 초기화한다.
4. while 반복을하며 vote 배열에서의 최댓값을 구한다. 최댓값을 max로, 최댓값의 위치를 index에 저장한다.
5. max가 dasom보다 크거나 같으면 최댓값에서 1을 뺀 후, dasom에 1을 더하고 counter를 증가시킨다.
6. max가 dasom보다 작으면, 반복문을 빠져나와 counter 값을 출력한다.

제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map(Number);

  const N = input[0];
  let dasom = input[1];
  let vote = input.slice(2, N+1);

  let counter = 0;

  while(true){
    let max = Math.max(...vote);
    let index = vote.findIndex(arg => arg === max);

    if(max < dasom)
      break;
    else{
      vote[index]--;
      dasom++;
      counter++;
    }
  }

  console.log(counter);

💡한줄평

이 문제를 스터디 시간에 간단하게 브레인스토밍을 통해 설계를 하는 과정에서 팀원 한 명이 최대히프 정렬을 사용해보는 것이 어떻냐는 말을 했었다. 직전학기 수업에서 배웠던 알고리즘을 떠올렸던 것이다. 그 말을 듣고 처음에는 최대 히프를 사용해서 해보려했으나 간단한 문제였기 때문에 코드가 더 복잡해진다는 생각이 들어 배열에서 최댓값을 구하는 방식으로 문제풀이를 했다. 그러나 최대히프 정렬이 조금 더 시간 단축엔 도움이 될 것 같다.