[Programmers] N으로 표현 - JAVA

1. 문제

프로그래머스

아래와 같이 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 함수를 작성하세요.

---

2. 풀이

dfs+dp방식으로 풀었다.

사용한 변수는 다음과 같다.

int len	number의 최솟값을 구하기 위해 필요한 최대 숫자. number*N으로 설정했다.
int[] dp	최솟값 저장 배열.
int[] NN	5,55,555처럼 N을 붙여서 만드는 숫자 저장. 인덱스는 N개수, 값에는 숫자가 저장된다.

 

solution

1.  len에 dp길이를 저장한다. number의 최솟값을 구하기 위해 필요한 최대 길이다. number*N으로 설정한 이유는 /N으로 최솟값을 만드는 경우가 있기 때문이다.

2.  dp를 len길이로 만들고 9로 채운다. 최솟값이 8초과이면 -1을 반환하기 때문에 dp에서는 9가 최댓값이다.

3.  NN배열을 8크기로 만든 후 N을 붙여서 만드는 숫자를 저장한다. 인덱스는 N의 개수, 값에는 숫자가 저장된다. 크기가 8인 이유는 최솟값이 8까지로 제한되었기 때문이다.

4.  dfs메서드를 호출한다.

5.  만약 dp[number]가 8보다 크다면 -1을 반환하고, 아니라면 dp[number]을 반환한다.

public int solution(int N, int number) {
    len = number*N;
    dp = new int[len+1];
    Arrays.fill(dp,9);
        
    NN = new int[9];
    for(int i=N, cnt = 1;cnt<9;i=i*10+N, cnt++) NN[cnt] = i;
        
    dfs(N,1);
        
    if(dp[number]>8) return -1;
    return dp[number];
}

 

dfs

1.  n이 범위에서 벗어났거나 현재 바꾸려는 cnt가 dp[n]에 저장된 수보다 크거나 같다면 그만둔다.

2.  dp[n]에 cnt를 저장한다.

3.  1부터 8까지 탐색하면서 재귀호출한다.

3-1.  만약 n이 NN[i]와 동일하다면 그 다음 NN[i+1]을 dfs에 넣고 호출한다.

3-2.  곱한 값으로 재귀호출한다. 이때 cnt는 cnt+N의개수(i)로 둬야 한다.

3-3.  더한 값으로 재귀호출한다.

3-4.  나눈 값으로 재귀호출하되, n이 NN[i]보다 크거나 같은 경우만 호출한다. 이 외의 경우는 n/NN[i]가 0이 되는데, 0은 N-N에서 최솟값을 이미 가질 수 있기 때문이다.

3-5.  뺀 값으로 재귀호출한다.

3-6.  n이 0이 아닐 때만 NN[i]를 n으로 나눠서 재귀호출한다. NN[i]-n도 0이 아닐때 호출한다. NN[i]-0=NN[i]라 의미가 없기 때문이다.

public void dfs(int n, int cnt){
    if(n<0 || n>len || dp[n]<=cnt) return;
    dp[n] = cnt;
    
    for(int i=1;i<9;i++){
        if(n==NN[i] && i<8) dfs(NN[i+1], cnt+1); 
        dfs(n*NN[i], cnt+i);
        dfs(n+NN[i], cnt+i);
        if(n>=NN[i]) dfs(n/NN[i], cnt+i);
        dfs(n-NN[i], cnt+i);
        if(n!=0) {
            dfs(NN[i]/n, cnt+i);
            dfs(NN[i]-n, cnt+i);
        }    
    }
}

 

전체 코드

import java.util.*;

class Solution {
    int[] dp, NN;
    int len;
    public int solution(int N, int number) {
        len = number*N;
        dp = new int[len+1];
        Arrays.fill(dp,9);
        
        NN = new int[9];
        for(int i=N, cnt = 1;cnt<9;i=i*10+N, cnt++) NN[cnt] = i;
        
        dfs(N,1);
        
        if(dp[number]>8) return -1;
        return dp[number];
    }
    
    public void dfs(int n, int cnt){
        if(n<0 || n>len || dp[n]<=cnt) return;        
        dp[n] = cnt;
        
        for(int i=1;i<9;i++){
        if(n==NN[i] && i<8) dfs(NN[i+1], cnt+1); 
            dfs(n*NN[i], cnt+i);
            dfs(n+NN[i], cnt+i);
            if(n>=NN[i]) dfs(n/NN[i], cnt+i);
            dfs(n-NN[i], cnt+i);
            if(n!=0) {
                dfs(NN[i]/n, cnt+i);
                dfs(NN[i]-n, cnt+i);
            }    
        }
    }
    
}

 

추가 - PriorityQueue활용한 버전

BFS처럼 풀었다.

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        int len = number*N;
        int[] NN = new int[9];
        for(int i=N, cnt = 1;cnt<9;i=i*10+N, cnt++){
            NN[cnt] = i;
        }
        
        boolean[] visited = new boolean[len+1];
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
        pq.offer(new int[]{N,1});
        
        int num,cnt,answer = -1;
        while(!pq.isEmpty()){
            num = pq.peek()[0];
            cnt = pq.poll()[1];
            if(num<0 || num>len || visited[num]) continue;
            if(cnt > 8) break;
            if(num==number){
                if(cnt<=8) answer = cnt;
                break;
            }
            visited[num] = true;
            
            for(int i=1;i<9;i++){
                if(num==NN[i] && i<8) pq.offer(new int[]{NN[i+1], cnt+1});
                pq.offer(new int[]{num*NN[i], cnt+i});
                pq.offer(new int[]{num+NN[i], cnt+i});
                if(num>=NN[i]) pq.offer(new int[]{num/NN[i], cnt+i});
                if(num>=NN[i]) pq.offer(new int[]{num-NN[i], cnt+i});
                if(num!=0) pq.offer(new int[]{NN[i]/num, cnt+i});
                if(num!=0) pq.offer(new int[]{NN[i]-num, cnt+i});
            }
        }
        
        return answer;
    }
    
}

---

3. 결과

왼쪽이 DFS+DP, 오른쪽이 PriorityQueue

dp+dfs가 시간이 훨씬 덜 든다. 메모리는 둘이 비슷하다.

queue를 활용하면 depth별로 접근해서 탐색이 빨라질 줄 알았지만 priorityqueue 내부에서 정렬하는 시간이 걸려서 더 느려진 것 같다.