[Programmers] 숫자 변환하기 - Java

문제

프로그래머스

 

풀이

x, y가 1에서 100만 사이의 값을 가지므로, 이중 for문과 같은 O(N^2)와 같은 풀이는 절대 안된다.

x, y가 좌표라고 치면 최소 이동거리를 계산을 하는 것이 변환하기 위한 최소 연산 횟수라고 생각했다.

최소 이동거리를 계산하기 위해서, bfs를 사용해서 현재 위치가 목표 위치가 되었을때, 최소 연산의 횟수를 구한다. 

 

소스코드

import java.util.*;

class Solution {
    private static class Point {
        int pos;
        int cnt;
        
        Point(int pos, int cnt) {
            this.pos = pos;
            this.cnt = cnt;
        }
    }
    
    public int solution(int x, int y, int n) {
        ArrayDeque<Point> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[1_000_001];
        
        int answer = Integer.MAX_VALUE;
        
        queue.addLast(new Point(x, 0));
        visited[x] = true;
        
        while (!queue.isEmpty()) {
            Point cur = queue.removeFirst();
            
            int pos = cur.pos;
            int cnt = cur.cnt;
            
            if (pos == y) {
                return cnt;
            }
            
            int nextPos = pos + n;
            
            if (1 <= nextPos && nextPos < 1_000_001) {
                if (!visited[nextPos]) {
                    queue.addLast(new Point(nextPos, cnt + 1));
                    visited[nextPos] = true;
                }
            }
            
            nextPos = pos * 2;
            
            if (1 <= nextPos && nextPos < 1_000_001) {
                if (!visited[nextPos]) {
                    queue.addLast(new Point(nextPos, cnt + 1));
                    visited[nextPos] = true;
                }
            }
            
            nextPos = pos * 3;
            
            if (1 <= nextPos && nextPos < 1_000_001) {
                if (!visited[nextPos]) {
                    queue.addLast(new Point(nextPos, cnt + 1));
                    visited[nextPos] = true;
                }
            }
        }
        
        return -1;
    }
}