프로그래머스_N으로 표현(JAVA)

https://programmers.co.kr/learn/courses/30/lessons/42895?language=java 

코딩테스트 연습 - 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 합니다.

입출력 예

 

N	number	return
5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2

11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

---

 

[문제 분석]

 

<변수 설명>

min : N을 가장 적게 사용한 횟수이고, 즉, 최솟값인데, 최종적으로 이 값이 8보다 크다면 -1을 return할 것이므로 9로 초기화시켜준다.

ans: number과 같은 값을 가진 전역변수

n: N과 같은 값을 가진 전역변수

 

해당 문제는 dfs를 이용하여 푸는 문제였다. 

구현한 dfs함수는 다음과 같다. dfs함수의 매개변수는 정수형 변수 count, cal 2개이다.

count는 n을 사용한 횟수이고, cal은 이전에 계산한 값을 의미한다.

 

이 문제에서 가장 해결하기 까다로웠던 부분은 숫자를 이어붙이는 것이 가능하다는 점이었다. 예를 들어, N=5라면, 55, 555, 5555 .... 처럼 수를 이어붙이는 것이 가능해 이를 언제 어떠한 방식으로 처리해주어야 하는 지가 어려웠다.

그래서 함수 dfs안에서 dfs를 다시 호출해주고 이 과정이 끝나면 n을 이어붙인 수인 temp(=temp*10+n)를 연산에 참여시켜 반복문을 다시 재개하는 방식으로 해결하였다. 처음 연산에 참여할 수는 n 그 자체이므로 temp는 n으로 초기화시킨다.

 

연산의 종류는 +, -, *, / 4가지이므로, 반복문 내에서 dfs를 4번 호출한다. 

반복문은 i=0부터 8-count보다 작을 때까지 수행할 것인데 이는 count가 8보다 넘어가면 더 이상 계산하는 의미가 없기 때문이다.

 

반복문 안에서 검사해야할 조건은 2가지이다.

1. 만약 count가 8보다 큰 수라면 return한다.

2. count가 8보다 작거나 같고, cal값이 ans와 같다면 n을 이용해서 ans를 표현한 것이므로 

    2-1. 현재의 min값과 count 값을 비교하여 min값보다 count값이 작다면 min 값을 count로 변경시키고 return 한다.

 

dfs가 모두 종료하고 solution 함수로 돌아왔을 때 min값이 8보다 크다면 -1을, 그렇지 않다면 min값을 return한다.

[코드]

class Solution {
    int ans;
    int min=9;
    int n;
    
    public void dfs(int count, int cal) {
        if(count>8) { 
            return;
        }
        
        if(cal==ans){
            if(min>count)
                min=count;
            return;
        }
        int temp=n;
        for(int i=0;i<8-count;i++){
            dfs(count+i+1, cal+temp);
            dfs(count+i+1, cal-temp);
            dfs(count+i+1, cal*temp);
            dfs(count+i+1, cal/temp);
            
            temp= temp* 10 + n;
}
        
        
    }    
    public int solution(int N, int number) {
        n=N;
        ans=number;
        dfs(0,0);
        if(min>8)
            min=-1;
        return min;
    }
}