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

링크

간단한 BFS 문제인 거 같다. 그래서 BFS 로 짰더니 시초가 났다. 방문 처리 또는 dp로 확장했다. 풀렸다. 끝

1트

import java.util.*;

class Solution {

    public int solution(int x, int y, int n) {
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                if (cur == y) {
                    return count;
                }
                if (cur + n <= y) {
                    queue.add(cur + n);
                }
                if (cur * 2 <= y) {
                    queue.add(cur * 2);
                }
                if (cur * 3 <= y) {
                    queue.add(cur * 3);
                }
            }
            count++;
        }
        return -1;
    }
}

시간 초과가 발생한 코드이다.

2트

import java.util.*;

class Solution {

    public int solution(int x, int y, int n) {
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.add(x);
        visited.add(x);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                if (cur == y) {
                    return count;
                }
                if (cur + n <= y && !visited.contains(cur + n)) {
                    queue.add(cur + n);
                    visited.add(cur + n);
                }
                if (cur * 2 <= y && !visited.contains(cur * 2)) {
                    queue.add(cur * 2);
                    visited.add(cur * 2);
                }
                if (cur * 3 <= y && !visited.contains(cur * 3)) {
                    queue.add(cur * 3);
                    visited.add(cur * 3);
                }
            }
            count++;
        }
        return -1;
    }
}

방문 처리를 통해서 이를 해결했다. 사실, 경로가 정해져있어서 dp로 풀면 되려나 싶기도 했다.

3트

import java.util.*;  
  
class Solution {  
    public int solution(int x, int y, int n) {  
        int[] dp = new int[y + 1];  
        Arrays.fill(dp, -1);  
        dp[x] = 0;  
        for (int i = x; i <= y; i++) {  
            if (dp[i] == -1) continue;  
            if (i + n <= y) {  
                if (dp[i + n] == -1) {  
                    dp[i + n] = dp[i] + 1;  
                } else {  
                    dp[i + n] = Math.min(dp[i + n], dp[i] + 1);  
                }  
            }  
            if (i * 2 <= y) {  
                if (dp[i * 2] == -1) {  
                    dp[i * 2] = dp[i] + 1;  
                } else {  
                    dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);  
                }  
            }  
            if (i * 3 <= y) {  
                if (dp[i * 3] == -1) {  
                    dp[i * 3] = dp[i] + 1;  
                } else {  
                    dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);  
                }  
            }  
        }  
        return dp[y];  
    }  
}

dp를 이용한 풀이

4트

가독성 개선

import java.util.*;

class Solution {

    public int solution(int x, int y, int n) {
        int[] dp = new int[y + 1];
        Arrays.fill(dp, y + 1);
        dp[x] = 0;
        for (int i = x; i <= y; i++) {
            if (dp[i] == y + 1) {
                continue;
            }
            if (i + n <= y) {
                dp[i + n] = Math.min(dp[i + n], dp[i] + 1);
            }
            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);
            }
        }
        return dp[y] == y + 1 ? -1 : dp[y];
    }
}

if 분기를 없앴다. y+1 로 초기화 해줘도 되는 게 맞나? 근데 패스는 했다.