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

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/154538#

프로그래머스

 

2. 접근 방식

 처음에 dfs로 접근을 시도하다 최소값을 찾는 조건을 다시 한번 확인하고 bfs로 바꿨다. 뭔가 계속 풀릴듯 안 풀릴듯 헤매다 결국 다른 사람의 정답을 보고 dp + bfs로 접근해야 함을 알게 됐다. dp만 잘 사용하면 굳이 bfs 방식으로 접근할 필요도 없을 듯하다.

 

가장 중요한 점은 dp를 활용하는 것이다.

y+1크기의 배열에 연산을 한 결과값을 인덱스로하는 원소에 연산 횟수를 최솟값으로 넣어준다. 

 

예를 들어 아래와 같은 길이 10의 배열이 있다. 이 때 x는 3, y는 9, n은 3이라 할 때

0

1

2

3

4

5

6

7

8

9

 

첫 번째 while문을 돌리면 연산 값은 6, 9, 6이 되며 배열의 원소는 아래와 같이 바뀐다.

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	1	0	0	1

연산 결과 값이 y보다 작으면 q에 넣어준다.

 

3. 구현

import java.util.*;

class Solution {
    static int[] result;
    
    public int solution(int x, int y, int n) {
        int answer = -1;
        int[] cal = {2, 3, n}; // 연산에 필요한 숫자 배열
        result = new int[y+1]; // 연산 횟수 최소값을 담는 배열
        bfs(x, y, n, cal);
        if (result[y] != 0) {
            answer = result[y];
        } else if (x == y) {
            answer = 0;
        }
        return answer;
    }
 
    public static void bfs(int x, int y, int n, int[] cal) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(x);
        
        while (!q.isEmpty()) {
            int temp = q.poll();
            int[] tempArr = new int[3]; // 연산 결과값을 담는 배열
            Arrays.fill(tempArr, temp);
            
            for (int i=0; i<cal.length; i++) {
                if (i == 2) {
                    tempArr[i] += cal[i]; // n일 경우 더해주고
                } else {
                    tempArr[i] *= cal[i]; // 나머지는 곱해주고
                } 
            }
            
            for (int i=0; i<cal.length; i++) {
                if (tempArr[i] > y) {
                    continue;
                }
                // result[tempArr[i]] > result[temp]+1 -> 최소값을 넣기 위한 조건
                if (result[tempArr[i]] == 0 || result[tempArr[i]] > result[temp]+1) {
                    result[tempArr[i]] = result[temp] + 1;  
                    q.add(tempArr[i]);
                }
            }
        }
    }
}

 

 

4. 정리

 처음 접근을 dfs로 하면서 꼬이고, 두 번째는 어떤 연산부터 실행할 지 고민하다가 완전 꼬여버렸다. 처음부터 dp로 접근할 생각했으면 좋았을 텐데 꼭 문제 풀때는 생각이 안난다.

 정답을 맞춘 후 다른 사람의 코드를 보다가 참 간결하고 명확하게 작성한 코드를 발견해 아래에 첨부한다. 세상엔 참 대단한 사람들이 많은 것 같다.

import java.util.*;

class Solution {

    int[] dp = new int[3000003];
    int INF = 1000002;

    public int solution(int x, int y, int n) {
        int answer = 0;
        Arrays.fill(dp, INF);
        dp[x] = -1;
        dp[y] = 0;
        for(int num = Math.max(y - n, Math.max(y / 2, y / 3)); num >= x; num--){
            dp[num] = Math.min(dp[num + n] + 1, Math.min(dp[num * 2] + 1, dp[num * 3] + 1));
        }
        return dp[x] >= INF ? -1 : dp[x];
    }
}