[Java] 프로그래머스(level-2) - 숫자 변환하기

문제 풀이

---

이번 문제는 동적 계획법(DP)을 통해 풀 수 있다.

처음엔 단순히 재귀를 통해 xn, x2, x*3 경우별로 재귀 호출하여 y가 되는 순간의 최소 깊이를 반환하는 방식으로 풀었으나 시간초과가 발생했다.

재귀 코드 - 오답(시간초과 발생)

class Solution {
    static int answer;
    public int solution(int x, int y, int n) {
        answer = Integer.MAX_VALUE;
        recursion(x, y, n, 0);
        if(answer == Integer.MAX_VALUE) {
            answer = -1;
        }
        return answer;
    }
    
    public static void recursion(int x, int y, int n, int depth) {
        if(x > y) {
            return;
        }
        if(x == y) {
            answer = Math.min(answer, depth);
        }
        recursion(x+n, y, n, depth+1);
        recursion(x*2, y, n, depth+1);
        recursion(x*3, y, n, depth+1);
    }
}

아이디어 도출

그렇다면 어떻게 시간초과를 줄일 수 있을까? 완전탐색을 하지 않고 효율적인 방법이 없는지를 고민해보니 DP 테이블에 x가 y로 변환되는 최소 연산횟수를 갱신해가며 접근하는 방법으로 풀 수 있다고 판단하여 DP를 이용해 풀 수 있었다.

DP를 이용한 아이디어를 살펴보자.

1. y만큼의 크기를 가지는 DP 테이블을 선언하고 x부터 y까지 순회하며 DP 테이블의 값을 갱신한다.
2. DP 테이블의 값을 갱신하는 경우는 index+n, index2, index3과 같이 3가지 경우로 나누어 DP 테이블의 원소를 기록한다.
3. 현재 위치의 DP 테이블 값이 변환될 수 없는 수라면 -1을 기록하고 순회를 넘어간다.

다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.

작성 코드

---

import java.util.*;

class Solution {

    // x와 y의 최대 범위 값을 상수로 활용한다.
    static final int MAX_VALUE = 1_000_000;

    public int solution(int x, int y, int n) {
        
        // DP 테이블을 MAX_VALUE 값으로 초기화한다.
        int[] D = new int[y+1];
        Arrays.fill(D, MAX_VALUE);

        // DP 테이블의 x번째 원소를 0으로 초기화한다.
        D[x] = 0;

        /**
         * DP 테이블에 연산 횟수를 갱신하는 반복문
         * x부터 y까지 순회하면서 x의 값에서 변환할 수 있는 i+n일 경우, i*2일 경우, i*3일 경우를 비교한다.
         * 변환할 수 없는 값이라면 
         * 변환할 수 있는 값일 경우 i번째 연산 횟수에서 1씩 증가한 값과 최솟값을 비교하여 갱신한다.
         */
        for(int i=x; i<=y; i++) {
            
            // 현재 위치의 x값이 y로 변환할 수 없다면 -1로 기록하고 넘어간다.
            if(D[i] == MAX_VALUE) {
                D[i] = -1;
                continue;
            }

            // 연산횟수를 기록한다.
            if(i + n <= y) {
                D[i+n] = Math.min(D[i+n], D[i]+1);
            }
            if(i * 2 <= y) {
                D[i*2] = Math.min(D[i*2], D[i]+1);
            }
            if(i * 3 <= y) {
                D[i*3] = Math.min(D[i*3], D[i]+1);
            }

        }
        
        return D[y];
    }

    public static void main(String[] args) {
        
        Solution sol = new Solution();
        
        int x = 10;
        int y = 40;
        int n = 5;
        
        sol.solution(x, y, n);

    }

}

회고

-

---

출처

-

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.