[JS][백준]1052_물병

문제 번호

 

1052번: 물병

 

 

알고리즘 분류

• 수학
• 구현
• 그리디 알고리즘
• 비트마스킹

 

문제 풀이

 처음에는 구입한 물병의 개수를 0개부터 1개씩 늘려가면서 조건에 맞는 답을 찾으려했다. 근데 이렇게 진행하면 시간초과에 걸린다. 문제를 풀고나서 다른언어들 풀이도 봤는데 다른언어들은 시간초과에 걸리지 않는거같았다.(왜 JS만....ㅠ)

 

 그래서 2진법을 활용해야한다. 주어진 N을 2진법으로 바꾸면 몇개의 물병을 들고가야하는지 알 수 있다. 만약 N이 8이라면 2진법으로 바꿨을때 1000(2) 가 된다. 즉 물병을 모두 합쳤을때 1개의 물병만 들고 갈 수 있게 된다는 뜻이다. 

 

 문제에서는 조건을 만족하지 못하는경우 '-1'을 반환하라고 했지만 실제로 조건을 만족하지 못하는 경우는 없다. 물병을 합칠때마다 같은양의 물이 들어있는 물병의 개수는 반(/2)으로 줄어드는데 추가적으로 구입할 수 있는 물병의 개수에는 제한이 없기떄문에 어떠한 경우든 총 물병의 개수를 '2의 제곱승 개'로 맞출 수 있기 때문이다.

 

 그래서 N을 2진법으로 전환하고 '1'이 몇개 나오는지 알아보고, 이 개수가 K개 이하이면 문제의 조건을 만족한다. 만약 '1'의 개수가 K개 보다 많다면 물병을 새로 구입해야한다. 2^0 자리부터 탐색해서 최초로 1이 나오는자리를 idx라고 하자. 이때 N에 '2**idx'를 더해준다. 이 과정을 통해서 '1'의 개수를 줄일 수 있는데, 이는 최종적으로 들고가야하는 물병의 개수를 줄이는 것과 같다. 

    let plus = 2**(idx);
    answer += plus;
    N += plus;

 위의 과정들을 반복해서 '1'의 개수가 K개 이하가 될때의 값을 반환하면된다. answer은 추가적으로 구입한 물병의 개수, N은 answer가 더해진 총 물병의 개수 이다.

 

전체코드

function main() {
  const input = require('fs').readFileSync('input.txt').toString().trim().split(' ').map(Number);
  let [N, K] = input;
  return console.log(sol(N,K));
}
function sol(N, K) {  
  let answer = 0; // 불가능한 경우는 없다.

  let bin = N.toString(2);
  let cnt=0;
  /**
   * N을 이진수로 바꿧을때 등장하는 '1'의 개수만큼 들고가야한다. 13개의 물병이 있다면 13을 2진수로 바꿧을때 1101 이 되므로 총 3개의 물병을 들고가야한다.
   * N을 이진수로 바꾸고 등장하는 '1'의 개수를 세어보고 K이하인지 확인하자.
   */
  for(let i=0; i<bin.length; i++) { 
    if(bin[i] === '1') cnt++;
  }

  while(cnt>K) {  // 물병의 개수가 초과된다면 물을 추가로 구입해야한다.
    let temp = Array.from(bin).reverse();
    let idx = 0;
    for(let i=0; i<temp.length; i++) {  // 처음으로 1이 발생하는 위치만큼 물을 더 사야 최종적으로 들고가는 물의 개수를 줄일 수 있다.
      if(temp[i] === '1') {
        idx = i;
        break;
      }
    }
    let plus = 2**(idx);
    answer += plus;
    N += plus;

    bin = N.toString(2);
    cnt=0;
    for(let i=0; i<bin.length; i++) {
      if(bin[i] === '1') cnt++;
    }
  }
  return answer;
}
main();

 

 

특이사항

  String 메서드중에 lastIndexOf() / indexOf()를 사용해보자.

 

String.prototype.lastIndexOf() - JavaScript | MDN