[JS][백준]17255_N으로 만들기

문제 번호

17255번: N으로 만들기

 

 

알고리즘 분류

• 자료 구조
• 백트래킹
• 트리를 사용한 집합과 맵

 

문제 풀이

 백트래킹을 활용하여 문제를 풀었다. 

 

 문제에서 주어진 수 N을 만들때 각 자리마다 시작하는 경우를 생각해보아야 한다. 4자리 숫자라면 1의 자리, 10의 자리, 100의 자리, 1000의 자리에서 시작할때를 각각 따져보아야 한다. 

  for (let i = 0; i < input.length; i++) {
    let t = '';
    let tmp = ''
    t += input[i];    
    sol(i, i, t, tmp);
  }

 

 그 후 숫자를 하나씩 붙여가면서 왼쪽에 숫자를 더 붙일 수 있는지 확인하고, 불가능 하다면 오른쪽에 숫자를 붙일 수 있는지 확인한다.

 같은 N을 만들더라도 만드는 과정이 다르면 다른 방법이므로 만드는 과정을 기록해야한다. tmp 라는 변수를 사용해서 현 단계 까지 만든 숫자(t)를 tmp에 계속 더해준다. N 이라는 숫자를 완성했다면 tmp를 answer 이라는 Set형 변수에 넣어주어서 중복을 방지하면서 경우의 수를 계산한다.

 tmp를 사용할때 origintmp 라는 변수도 같이 사용한다. 백트래킹 방법을 사용하였는데 tmp는 문자열 형식이기 때문에 tmp에 숫자(t)를 붙여준다음 다시 빼주기가 어려웠다. 따라서 temp에 t를 더하기전의 temp를 origintmp라고 하여서 함수호출이 끝나고 돌아올때 tmp를 t를 더하기 전의 상태로 돌려준다.

if(l-1 >= 0){
      let origintmp = tmp;
      tmp += t;
      sol(l-1,r,input[l-1]+t,tmp);      
      tmp = origintmp;
    }
    if(r+1<input.length){
      let origintmp = tmp;
      tmp += t; 
      sol(l,r+1,t+input[r+1],tmp);      
      tmp = origintmp;
    }

 

 

 왼쪽, 오른쪽에 문자열 추가가 가능한지 알아볼때 input[l-1]+t // t+input[r+1] 처럼 사용하여서 보이는 그대로 작동하도록 하였다.

 

 

 

 

전체 코드

const fs = require('fs').readFileSync('N으로 만들기/input.txt');
const input = fs.toString().trim().split('');

let answer = new Set();

function sol(l, r, t, tmp) {
  if (l === 0 && r === input.length - 1){ 
    tmp += t;   
    return answer.add(tmp)
  }
  else{
    if(l-1 >= 0){
      let origintmp = tmp;
      tmp += t;
      sol(l-1,r,input[l-1]+t,tmp);      
      tmp = origintmp;
    }
    if(r+1<input.length){
      let origintmp = tmp;
      tmp += t; 
      sol(l,r+1,t+input[r+1],tmp);      
      tmp = origintmp;
    }
  }
}

function insert() {
  for (let i = 0; i < input.length; i++) {
    let t = '';
    let tmp = ''
    t += input[i];    
    sol(i, i, t, tmp);
  }
  console.log(answer.size);
}

insert();

특이사항

 트리 map?