[알고리즘] 백준 16953 A->B (javascript)

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

 

 

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

 

 

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

 

나의 첫 번째 풀이

let fs = require('fs')
let [goal,number] = fs.readFileSync('/dev/stdin').toString().split(' ').map(Number)


let count = 1;

const func = (input)=>{
    if(input%2===0){
        let a = input/2
        count++;
        if(a===goal){
            return;
        }
        func(a)
    }else {
        let str = input.toString()
        if(str[str.length-1]!=="1"){
            count = -1
            return;
        }else{
            let b = parseInt(str.substring(0,str.length-1))
            count++;
           if(b===goal){
               return;
           }
            func(b)
        }
    }
}
func(number)
console.log(count)

이 방법은 재귀 함수를 이용했다.

일단 아이디어는 이렇다.

2를 곱했거나, 맨 뒤에 1을 붙인 경우만 있으므로 다시 2로 나누어지거나 혹은 맨 뒤가 1인 경우만 있어야 한다.

이 두 케이스에서 모두 벗어나면 -1로 반환하면 된다.

따라서 일단 2로 나누고, 카운트를 올렸다. 그리고 해당 값이 골인지 비교하고, 골이 아니라면 다시 재귀적으로 함수를 불렀다.

만약 2로 나눠지지 않는 값이라면 맨 끝자리가 1인지 확인했다. 1이라면 1을 잘라주고 카운트를 올렸다. 그리고 해당 값이 골인지 비교하고 골이 아니라면 다시 재귀적으로 함수를 부르는 것이다.

이 방법은 내가 수학적 접근을 전혀 못했다. 아래 방법이 좀 더 심플하다.

 

 

 

나의 두 번째 풀이

let fs = require('fs')
let [goal,number] = fs.readFileSync('/dev/stdin').toString().split(' ').map(Number)


let count = 1;

 while (number > goal) { 
        if (number % 2 === 0) {
            number = number / 2;
        } else if (number % 10 === 1) {
            number = Math.floor(number / 10);
        } else {
            count = -1; 
            break;
        }
        count++;
    }

    if (number !== goal) {
        count = -1;  
    }

console.log(count)

이번에는 굳이 재귀함수를 사용하지 않았다.

사실 아이디어는 똑같은데, 같은 아이디어로 재귀함수를 불렀음에도 스택오버플로우 오류가 나면서 통과하지 못했다.

그래서 반복문만으로 풀었다.

 

추가된 아이디어는 맨 뒷자리가 1인것을 확인하려면, 10으로 나눈 나머지가 1이면 된다는 것이다..

그리고 1을 지우고 싶다면 10으로 나눈 몫만 챙기면 되는 것이다.

그런데 이 아이디어만 적용해서 재귀함수를 돌렸을때는 왜인지 모르겠지만 스택오버플로우가 발생하여 문제를 해결하지 못했다.

 

그래서 나는 반복문만으로 문제를 해결했다.

반복 조건은 number가 goal보다 큰 경우에만 돌게 되어있고, 만약 같아졌다면 반복하는 동안 더해진 카운트만 보일 것이고, 작아져버렸다면 이는 정답을 구할 수 없는 것이므로 -1로 반환했다.