[코딩테스트] - 숫자 변환하기LV2 ( 프로그래머스(programmers) / java )👍

안녕하세요 나홀로전세집입니다.

 

오늘은 레벨2 숫자 변환하기를 풀어보겠습니다.

 

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

프로그래머스

 

문제 설명

 

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

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

 

 

저는 문제를 보자마자 dfs 를 사용해 풀어야겠구나 라고 생각을 했습니다.

 

class Solution {
    public int minValue = 2100000000; // int 의 최댓값

    public int solution(int x, int y, int n) {
        dfs(x, y, n, 0);
        if (minValue == 2100000000) { // 최댓값까지 가도 y를 못만들면
            return -1;
        } else { // y를 만들었을 때
            return minValue;
        }
    }

    public void dfs(int x, int y, int n, int count) {
        if (x == y) { // x와 y가 같을 때
            minValue = count;
            return;
        }
        if (x > y || count >= minValue) { // y가 더 x보다 더 크면
            return; // x를 y로 만들 수 없다
            // 카운트가 최솟값보다 크면 더이상 진행일 필요도 없다
        }
        dfs(x + n, y, n, count + 1);
        dfs(x * 2, y, n, count + 1);
        dfs(x * 3, y, n, count + 1);
    }
}

그래서 다음과 같이 코드를 짜고 실행을 해봤습니다.

 

Oops! 시간초과!

 

단순 dfs만 사용하여 코딩했을 때는 시간초과가 났습니다.

 

이를 해결하기 위해서 방문 여부를 체크하는 코드를 추가했습니다. 

 

class Solution {
    public int minValue = 2100000000; // int 의 최댓값
    public boolean[][] visited; // 방문 여부를 저장 할 배열

    public int solution(int x, int y, int n) {
        visited = new boolean[y + 1][n + 1]; // x와 n의 최댓값을 고려하여 배열 초기화
        dfs(x, y, n, 0);
        if (minValue == 2100000000) { // 최댓값까지 가도 y를 못만들면
            return -1;
        } else { // y를 만들었을 때
            return minValue;
        }
    }

    public void dfs(int x, int y, int n, int count) {
        if (x == y) { // x와 y가 같을 때
            minValue = Math.min(minValue, count);
            return;
        }
        if (x > y || count >= minValue || visited[x][count]) { // y가 x보다 크거나 최소값보다 count가 클 때, 이미 방문한 적이 있는 경우
            return; // x를 y로 만들 수 없다
        }
        visited[x][count] = true; // 방문 여부 표시
        dfs(x + n, y, n, count + 1);
        dfs(x * 2, y, n, count + 1);
        dfs(x * 3, y, n, count + 1);
    }
}

방문 여부를 체크하는 배열을 추가했습니다

 

아...

방문 여부 배열을 만드니 메모리 초과가 떴습니다...

이러면 dfs를 포기하고 이 전 상태를 기억하는 DP를 사용해서 시간을 줄여보겠습니다.

 

class Solution {
    public int solution(int x, int y, int n) {

        int[] dp = new int[y + 1];
        for (int i = 0; i <= y; i++) {
            dp[i] = 2100000000;
        }

        dp[x] = 0; // 초기값 설정

        for (int i = x; i <= y; i++) {
            int plus = i + n;
            int x2 = i * 2;
            int x3 = i * 3;

            if (plus <= y) { // x에 n을 더하는 경우
                if (dp[plus] > dp[i] + 1) {
                    dp[plus] = dp[i] + 1;
                }
            }
            if (x2 <= y) { // x를 2배 하는 경우
                if (dp[x2] > dp[i] + 1) {
                    dp[x2] = dp[i] + 1;
                }
            }
            if (x3 <= y) { // x를 3배 하는 경우
                if (dp[x3] > dp[i] + 1) {
                    dp[x3] = dp[i] + 1;
                }
            }
        }

        if (dp[y] == 2100000000) // 목표값에 도달할 수 없는 경우
            return -1;
        else
            return dp[y];
    }
}

DP를 사용해 풀어봤습니다. DP 배열에는 x에 더하거나 곱해진 카운트를 넣었습니다. int 이기에 배열의 값을 모두 21억으로 최대값으로 입력해주었습니다.

 

나이스

DP를 사용해 dfs에서 나왔던 시간초과, 런타임에러, 메모리 초과를 해결하였습니다.

오랜만에 코테를 푸니 조금 어려웠던 것 같습니다.

 

 

 

 

전체 코드

class Solution {
    public int solution(int x, int y, int n) {

        int[] dp = new int[y + 1];
        for (int i = 0; i <= y; i++) {
            dp[i] = 2100000000;
        }

        dp[x] = 0; // 초기값 설정

        for (int i = x; i <= y; i++) {
            int plus = i + n;
            int x2 = i * 2;
            int x3 = i * 3;

            if (plus <= y) { // x에 n을 더하는 경우
                if (dp[plus] > dp[i] + 1) {
                    dp[plus] = dp[i] + 1;
                }
            }
            if (x2 <= y) { // x를 2배 하는 경우
                if (dp[x2] > dp[i] + 1) {
                    dp[x2] = dp[i] + 1;
                }
            }
            if (x3 <= y) { // x를 3배 하는 경우
                if (dp[x3] > dp[i] + 1) {
                    dp[x3] = dp[i] + 1;
                }
            }
        }

        if (dp[y] == 2100000000) // 목표값에 도달할 수 없는 경우
            return -1;
        else
            return dp[y];
    }
}

 

 

오늘도 즐코딩 하시고 좋은 하루 되세요~