[프로그래머스] 숫자 변환하기

https://school.programmers.co.kr/learn/courses/30/lessons/154538#

문제요점

• 세 연산의 모든 조합
• 숫자가 y초과하면 더이상 연산할 필요없다

 

첫번째 풀이 bfs (성공)

 

• 최소 연산 횟수 => bfs 를 생각했다.
• y가 x로 변환하는 방법
• x미만의 결과가 나오는 연산은 고려할 필요없다
• 최소연산 횟수 만에 찾기위해 num /3, num/2, num-n 순으로 찾았다.

function solution(x, y, n) {
    const queue = [{num: y, count: 0}];
    
    while(queue.length) {
        const {num, count} = queue.shift(); // shift는 O(n);
        // x가 되는 연산을 찾음
        if (num === x) {
            return count;
        }
        if (num % 3 === 0) {
            queue.push({num: num/3, count: count+1});
        }
        if (num % 2 === 0) {
            queue.push({num: num/2, count: count+1});
        }
        if (num-n >= x) {
            queue.push({num: num-n, count: count+1});
        }
    }
    return -1;
}

 

 

10번 테케가 상당히 오래걸렸다.

 

---

두번째 풀이 dp (성공)

시간을 줄이기 위해 dp로 수정해보았다.

dp[i] : i값에 도달하기 위한 최소 횟수

 

y+1 빈 배열을 생성하고 Inifity로 최소횟수를 init한다

dp[x] = 0으로 초기화하고 

순회하며 x 이후부터 y까지 dp배열을 채운다

dp[y] 값을 리턴한다.

 

function solution(x, y, n) {
    if (x === y) return 0; // 이미x,y의 값이 같을때
    const dp = Array.from({length: y+1}, () => Infinity);
    dp[x] = 0; 
    
    for (let i = x; i <= y; ++i) {
        if (dp[i+n]) {
            dp[i+n] = Math.min(dp[i+n], dp[i]+1);
        }
        if (dp[i*2]) {
            dp[i*2] = Math.min(dp[i*2], dp[i]+1);
        }
        if (dp[i*3]) {
            dp[i*3] = Math.min(dp[i*3], dp[i]+1);
        }
    }
    return dp[y] === Infinity ? -1 : dp[y];
}

 

---

🚀 세번째 풀이 (성공, 속도 향상)

x에서 y로 상향식 진행을 할 경우
3x, 2x, x+n 은 모두 정수가 되기 때문에
따져봐야 할 경우의 수가 많지만

 

y에서 x로 하향식 진행을 하면
y/3, y/2, y-n 은 적은 경우에만 정수가 되기 때문에 가지치기 속도가 향상 된다.

 

정수인지 확인하기

- Number.isInteger()
- 모듈러 연산 = 0

 

function solution(x, y, n) {
    const dp = Array.from({length: y+1}, () => Infinity);
    dp[y] = 0;
    
    for (let i = y; i >= x; --i) {
        if (i % 3 === 0) {
            const divideByThree = i/3;
            dp[divideByThree] = Math.min(dp[i]+1, dp[divideByThree]);
        }
        if (i % 2 === 0) {
            const divideByTwo = i/2;
            dp[divideByTwo] = Math.min(dp[i]+1, dp[divideByTwo]);
        }
        if (i - n >= x) {
            const subtractN = i-n;
            dp[subtractN] = Math.min(dp[i]+1, dp[subtractN]);
        }
    }
    return dp[x] === Infinity ? -1 : dp[x];
}

 

 

 

풀이

bfs

• y를 x로 변환하는 세 연산의 조합 중 가장 빨리 x가 되는 경우의 연산횟수를 리턴한다.
• 먼저 {num: y, count: 0}로 시작
• num/3이 정수이면 queue에 {num: num/3, count: count+1}를 push한다
• num/2이 정수이면 queue에 {num: num/2, count: count+1}를 push한다
• num-n이 x보다 크거나 같으면 queue에 {num: num-n, count: count+1}를 push한다

dp

• dp를 y+1 길이의 배열로 초기화한다. 각 배열의 값은 i가 되기까지 최소연산횟수이고 초기값은 Infinity다
• dp[y] = 0이다 (y에서 연산을 시작한다.)
• for문에서 i = y에서 i >= x까지 순회하며 가능한 경우를 dp에 갱신한다.
  • dp[i] = Math.min(dp[i], dp[i의 하향식 세가지 연산] + 1)

 

배운점

• bfs를 사용하면 모든 경우를 비교할 필요없이 가장 먼저(최소) 만족하는 답을 찾을 수 있다.
• 시간초과 => dp나 hash 사용
• dp[i] = i값에 도달하기 위한 최소값
• 하향식 진행 (y -> x)
• 가장 빠른 탐색을 위해 큰 연산 먼저 수행