프로그래머스 숫자 변환하기 자바 풀이

문제 링크

문제 요약

자연수 x를 y로 바꾸는 데 x+n, x2, x3 세 가지 연산을 쓸 수 있다
x를 y로 바꾸는 최소 연산 횟수를 구하는 문제다
만들 수 없으면 -1을 반환한다

문제 풀이

처음에는 x에서 시작해서 세 가지 연산을 재귀적으로 다 시도해보고 y에 도달하는 경로 중 가장 짧은 걸 고르면 되겠다고 생각했다.

하지만 y가 최대 1,000,000이고 매 단계마다 선택지가 3개씩 늘어나기 때문에, 모든 경로를 다 확인하면 경우의 수가 너무 커진다.

게다가 재귀로 아무 순서나 먼저 도달한 경로가 최소 횟수라는 보장도 없다.

이 문제의 핵심은 최소 횟수를 구하는 문제이므로, 값이 아니라 연산 횟수를 기준으로 한 칸씩 넓혀가는 BFS를 쓰면 y에 처음 도달하는 순간이 곧 최소 횟수라는 점이다.

큐에는 (현재 값, 지금까지 쓴 연산 횟수)를 같이 넣는다
세 연산으로 만들 수 있는 다음 값 중 y를 넘어서는 값은 애초에 버려서 탐색 범위를 y 이하로 제한한다
visited 배열로 이미 방문한 값은 다시 큐에 넣지 않아 중복 탐색을 막는다
큐에서 꺼낸 값이 y와 같으면 그 자리에서 바로 count를 반환한다

큐가 다 빌 때까지 y에 도달하지 못하면 만들 수 없는 경우이므로 -1을 반환한다.

최종 코드

java

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        Deque<int[]> q = new ArrayDeque<>();
        boolean[] visited = new boolean[y + 1];

        q.add(new int[]{x, 0});
        visited[x] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();

            int value = now[0];
            int count = now[1];

            if (value == y) {
                return count; // BFS이므로 처음 도달하는 순간이 최소 횟수
            }

            int[] next = {
                value + n,
                value * 2,
                value * 3
            };

            for (int nextValue : next) {
                if (nextValue > y) {
                    continue; // y를 넘어서면 탐색할 필요가 없다
                }
                if (visited[nextValue]) {
                    continue; // 이미 방문한 값은 다시 큐에 넣지 않는다
                }

                visited[nextValue] = true;
                q.add(new int[]{nextValue, count + 1});
            }
        }

        return -1;
    }
}

숫자 변환하기

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

두 원 사이의 정수 쌍