숫자 변환하기 [자바]

 

🧫 문제 분석

✔️ 출처

숫자 변환하기 level 2

📖 문제

 

간단하지만 생각해볼게 좀 있는 문제

최단경로 BFS로 풀어보자고 생각했다.

 

핵심

x == y 일때,

x로 y를 만들 수 없을때 bfs 탐색을 멈추는 조건

중복 탐색 방지 (시간 초과 가능성)

---

🔅 문제 풀이

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    // x -> y
    // x + n || x * 2 || x * 3
    //bfs 최단 경로 
    
    boolean[] visited = new boolean[1000001];
    
    public int solution(int x, int y, int n) {
        int answer = bfs(x,y,n);

        return answer;
    }

    private int bfs(int x, int y, int n) {
        Queue<int[]> q = new LinkedList<>();

	// 처음부터 안되는 경우 배제
        if (y % 2 == 0 || y % 3 == 0 || y % n == x || y % n == 0) {
            q.add(new int[]{x, 0});
        }

        while(!q.isEmpty()) {
            int[] current = q.poll();
            
            // y값이면 반환하고 종료
            if (current[0] == y) {
                return current[1];
            }
            // 값 체크 및 중복 방문 체크
            if (current[0] + n <= y && !visited[current[0] + n]) {
                q.add(new int[] {current[0] + n, current[1] + 1});
                visited[current[0] + n] = true;
            }
            if (current[0] * 2 <= y && !visited[current[0] * 2]) {
                q.add(new int[] {current[0] * 2, current[1] + 1});
                visited[current[0] * 2] = true;
            }

            if (current[0] * 3 <= y && !visited[current[0] * 3]) {
                q.add(new int[] {current[0] * 3, current[1] + 1});
                visited[current[0] * 3] = true;
            }
        }
        return -1;

    }
}

 

🔅 리팩토링

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    boolean[] visited = new boolean[1000001];
    Queue<int[]> q = new LinkedList<>();
    
    public int solution(int x, int y, int n) {
        int answer = bfs(x,y,n);
        return answer;
    }
    
    private int bfs(int x, int y, int n) {
        q.add(new int[]{x, 0});
        
        while(!q.isEmpty()) {
            int[] current = q.poll();
            // y값이면 반환하고 종료
            if (current[0] == y) return current[1];
            
            checkBound(current[0] + n, y, current[1]);
            checkBound(current[0] * 2, y, current[1]);
            checkBound(current[0] * 3, y, current[1]);
        }
        return -1;
    }
    
    private void checkBound(int value, int y, int count) {
        if (value <= y && !visited[value]) {
            q.add(new int[] {value, count + 1});
            visited[value] = true;
        }
    }
}

 

❗ 오답노트 / 필요한 지식

1. 일단 먼저 돌아가는 코드 만들기