숫자 변환하기 문제

문제

풀이

bfs 사용

(1). 메모리 초과

문제를 보자마자 '아 bfs를 사용해서 풀면 되는 간단한 문제군'이라 생각하고 코드를 짰다.

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = -1;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[] {x,0});
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            if(cur[0] == y) {
                answer = cur[1];
                break;
            }
            if(cur[0]*2 <= y) {
                queue.add(new int[] {cur[0]*2, cur[1]+1});
            }
            if(cur[0]*3 <= y) {
                queue.add(new int[] {cur[0]*3, cur[1]+1});
            }
            if(cur[0]+n <= y) {
                queue.add(new int[] {cur[0]+n, cur[1]+1});
            }
        }
        return answer;
    }
}

그러나 이 코드는 여러 개의 테스트 케이스에서 메모리 초과 의 결과를 얻었다.

(2). 방문 배열 visited[] 활용

방문배열을 활용해주면 메모리 초과를 해결할 수 있다.

visited의 true/false 여부를 확인하여, 앞서 이미 Queue에 넣었던 수에 대해서는 다시 넣지 않는다.
→ 앞서 넣었던 수의 cnt가 무조건 작다는 것이 보장되어야 한다. 어떻게 보장되는가?
→ DFS가 아닌 BFS이므로, 이미 해당 숫자가 도출된 적이 있다면 그 때의 cnt가 더 작거나, 적어도 같다.

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = -1;
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[y+1];
        queue.add(new int[] {x,0});
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            visited[cur[0]] = true;
            if(cur[0] == y) {
                answer = cur[1];
                break;
            }
            if(cur[0]*2 <= y && !visited[cur[0]*2]) {
                queue.add(new int[] {cur[0]*2, cur[1]+1});
            }
            if(cur[0]*3 <= y && !visited[cur[0]*3]) {
                queue.add(new int[] {cur[0]*3, cur[1]+1});
            }
            if(cur[0]+n <= y && !visited[cur[0]+n]) {
                queue.add(new int[] {cur[0]+n, cur[1]+1});
            }
        }
        return answer;
    }
}

이미 계산된 적 있는 숫자에 대해선 다시 계산하지 않으므로, 쓸데없는 연산을 줄여 메모리 초과에서 벗어났다.

dp 사용

bfs를 사용해서 제출하고 메모리 초과가 떴을 때, dp를 사용한 풀이를 생각해보았다.
그런데 dp 문제를 푼 지 오래되어서일까 .. 쉽게 떠오르지 않아 포기하고 다시 bfs로 우회했다.

문제를 풀고 나서 dp를 사용한 풀이들을 보니, 확실히 이 문제는 dp를 사용하는 것이 더 성능이 좋음을 확인했다.

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int[] dp = new int[y+1];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[x] = 0;
        for(int i=x; i<=y; i++) {
            if(dp[i] == Integer.MAX_VALUE) continue;
            // 아직 도달하지 않은 숫자는 건너뛴다.
            if(i * 2 <= y) {
                dp[i*2] = Math.min(dp[i*2],dp[i]+1);
            }
            if(i * 3 <= y) {
                dp[i*3] = Math.min(dp[i*3],dp[i]+1);
            }
            if(i + n <= y) {
                dp[i+n] = Math.min(dp[i+n],dp[i]+1);
            }
        }
        return dp[y] == Integer.MAX_VALUE ? -1 : dp[y];
    }
}

• dp[i]는 숫자 i에 도달하는 데 필요한 최소 연산 횟수를 나타낸다.
  → 따라서 dp[x] = 0이다.
• x부터 시작하여 x*2,x*3,x+n의 dp를 확인하고, 현재 연산 횟수에서 +1 한 값 (= dp[i]+1 ) 이 더 작다면 업데이트해준다.
• y의 값을 확인하여 리턴한다.

• x부터 y까지 상수 시간만큼만 연산을 하면 되므로 각 테스트에 대한 시간의 편차가 적음을 확인할 수 있다. worst case일 때와 best case일 때의 시간/메모리 차가 적다.

---

1. bfs 사용 시 메모리 & 시간 초과가 뜬다면 방문 배열을 사용할 것
2. dp 문제 꾸준히 풀자 ...