[JS][백준]16943_숫자 재배치

문제 번호

16943번: 숫자 재배치

 

 

 

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 조합론

 

문제 풀이

 주어진 숫자 A로 만들수 있는 모든 숫자들을 만들어보고 조건에 맞는지 확인하면된다.

조건은 A를 이루는 숫자들을 모두 사용해야하고, 그 결과물이 B보다 작아야한다. 

브루트포스 알고리즘을 사용해서 문제를 해결하였으나 DFS를 통하여 풀이를 진행해도 가능하다.

 

전체코드

let s = [];
let answer = -1;

function check(s, b, n){  
  s = Number(s.join(''));  
  if(s.toString().length !== n)
    return -1;
  if(s < b && s > answer)
    answer = s;  
}

function sol(A, b, visited) {
  if (s.length === A.length)
    return check(s, b, A.length);

  for (let i = 0; i < A.length; i++) {
    if (!visited[i]) {
      s.push(A[i]);
      visited[i] = true;
      sol(A, b, visited);
      s.pop();
      visited[i] = false;
    }
  }

}

function insert() {
  const input = require('fs').readFileSync('숫자 재배치/input.txt').toString().trim().split(' ').map(Number);
  let [a, b] = input.slice(0, 2);
  let A = a.toString().split('').map(Number);  
  //console.log(A)
  let visited = new Array(A.length).fill(false)
  sol(A, b, visited);
  console.log(answer);
}
insert();

 

특이사항