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

프로그래머스 숫자 변환하기 Java 풀이에 대해 알아보겠습니다.

Table of Contents

프로그래머스 – 숫자 변환하기 경로

코딩테스트 연습 > 연습문제 > 숫자 변환하기

문제 설명 및 제한사항

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

x에 n을 더합니다
x에 2를 곱합니다.
x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항

1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

입출력 예 설명

입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

숫자 변환하기 Java 풀이

사실 이 문제는 BFS랑 DP 두 알고리즘 모두의 성격을 띄고 있다고 생각하지만, 배열 이름은 편의상 dp로 하겠습니다 🙂

주석을 읽어보시면 이해가 되실거에요~!

class Solution {
    public int solution(int x, int y, int n) {
        //우선 탐색이 필요한 최댓값은 y이기 때문에, 인덱싱 편의상 y + 1 만큼의 배열을 만들어줍니다.
        int[] dp = new int[y + 1];

        dp[x] = 1; // 시작점 초기화 (마지막에 뺄 예정)

        for(int i = x; i <= y; i++) {
            // 방문한 이력이 없으면 무시하고 다음 위치로 넘어갑니다.
            if(dp[i] == 0)
                continue;

            // 아래 공통 규칙을 고수합니다.
            // 목적지가 y 값 이하여야 합니다.
            // 이동하려는 위치의 값(이동 카운트)이 0이거나, 현재 이동 카운트 + 1 보다 클때만
            // 현재 이동 카운트 + 1을 해줍니다. 
            if(i + n <= y && (dp[i + n] == 0 || dp[i + n] > dp[i] + 1))
                dp[i + n] = dp[i] + 1;

            if(i * 2 <= y && (dp[i * 2] == 0 || dp[i * 2] > dp[i] + 1))
                dp[i * 2] = dp[i] + 1;

            if(i * 3 <= y && (dp[i * 3] == 0 || dp[i * 3] > dp[i] + 1))
                dp[i * 3] = dp[i] + 1;

        }
        return dp[y] == 0 ? -1 : dp[y] - 1; // 초기화 해줬던 1 제외
    }
}

결과

개발자 면접 질문 – Java

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