[프로그래머스] N으로 표현 (Dynamic Programming)-JAVA

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

[문제 설명]

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

 

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

 

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

[제한 사항]

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

[풀이]

재귀를 활용하여 해당 문제를 해결하였다. 여기서 주의할 점은 최솟값이 8보다 크면 -1을 return 한다는 점이다. 즉, 코드를 수행하면서 구하고자하는 수가 8보다 클 경우 바로 이전으로 리턴하여 시간복잡도를 줄였다. 

 

재귀가 발생하는 코드는 총 4개로 구성하였다. 그 이유는 사칙연산이 가능한 연산자가 위 제한 사항에 의하면 4가지 이기 때문이다(+,-,*,/). 

 

문제를 해결하는 과정에서 가장 핵심은 문제 설명 예시의 '55'처럼 붙어 있는 숫자들을 어떻게 처리할지인데, 해당 문제는 for문으로 돌리면서 특정 변수에 N값이 지속적으로 쌓일 수 있도록 설정하였다. 예를들어 첫번째 for문 때는 '5' 두번째는 '55' 세번째 때는 '555'처럼 말이다. 물론 해당 위치에 '555'가 들어간다면 뒤에 공간들에선 5가 최대 5번밖에 들어갈 수 없다. 

 

    private static void getReturn(int cnt, int n, int target,int sum) {
        if(cnt>8){
            return;
        }

        if (sum == target) {
            answer = Math.min(answer, cnt);
            return;
        }

        int temp=0;
        for (int i = 0; i < 8; i++) {
            temp = temp*10+n;
            getReturn(cnt+i+1,n,target,sum+temp);
            getReturn(cnt+i+1,n,target,sum-temp);
            getReturn(cnt+i+1,n,target,sum/temp);
            getReturn(cnt+i+1,n,target,sum*temp);
        }

    }

위 코드처럼 총 N이 몇번 나왔는지를 의미하는 cnt가 8이 넘어갈 경우 return을 통해 이전으로 돌아갈 수 있도록 하였다. 또한 for문 속 temp가 지속적으로 N을 쌓이게 하는 역할을 수행하며, cnt+i+1이라는 코드를 통해 최대 N이 나올 수 있는 갯수를 한정하였다. 

 

최종 코드는 다음과 같다.

 

class Solution {

    static int answer = Integer.MAX_VALUE;
    
    public int solution(int N, int number) {
        getReturn(0,N, number,0);
        
        if(answer == Integer.MAX_VALUE){
            return -1;
        }else{
            return answer;
        }
    }

    private static void getReturn(int cnt, int n, int target,int sum) {
        if(cnt>8){
            return;
        }

        if (sum == target) {
            answer = Math.min(answer, cnt);
            return;
        }

        int temp=0;
        for (int i = 0; i < 8; i++) {
            temp = temp*10+n;
            getReturn(cnt+i+1,n,target,sum+temp);
            getReturn(cnt+i+1,n,target,sum-temp);
            getReturn(cnt+i+1,n,target,sum/temp);
            getReturn(cnt+i+1,n,target,sum*temp);

        }

    }
}