Node.js)백준 16936번: 나3곱2 ★

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

16936번: 나3곱2

 

★은 다시 풀어볼 문제  =>  브루트포스로 다시 풀기 

 

 

브루트포스로 분류되는 문제인데. 브루트포스로 풀다가 계속 틀려서

질문 https://www.acmicpc.net/board/view/57079  을 보고 힌트를 얻어서 방식을 바꿔서 풀었다. 

 

3을 인수로 많이 갖는 수를 앞에 배치한다. 

3을 똑같이 가지고 있다면. 3을 제외한  나머지 인수들의 곱이 작은 값이 앞에 배치된다. 

ㅁ

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n").map(v=>v.split(' ').map(x=>BigInt(x)));
const nums = input[1];
const test = [];
nums.forEach(v=>{
  const {three,leftover} = haveThree(v)
  test.push({value:v,three,leftover})
})

const answer = test.sort((a,b)=>{
  if(b.three>a.three){
    return 1;
  }else if(b.three<a.three){
    return -1;
  }else{
    if(a.leftover>b.leftover){
      return 1;
    }else{
      return -1
    }
  }
}).map(v=>v.value).join(' ')
console.log(answer)



function haveThree(n){
  let three = BigInt(0);
  while(true){
    if(n%BigInt(3)==BigInt(0)){
      three++;
      n/=BigInt(3);
    }else{
      break;
    }
  }
  return {
    three,
    leftover:n
  }
}