N으로 표현 JAVA

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

프로그래머스

아래와 같이 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의 사용횟수가 최소가 되도록 number를 만드는 것이다.

처음에는 백트레킹으로 구현하였는데, 구현에 어려움을 느껴 포기하고 DP를 이용했다.

아래의 코드는 내가 처음에 접근한 DP 방식이다.

dp[i] = N과 사칙연산을 최소로 활용한 N의 사용횟수이다.

import java.util.*;
class Solution {
    static int[]arr;
    public int solution(int N, int number) {
        arr = new int[6];
        for(int i=1;i<=5;i++){
            arr[i] = arr[i-1] * 10 + N; //arr배열에는 중복 N이 들어감
        } //arr[1] = 5, arr[2] = 55 ...
        
        int []dp = new int[10000000];
        for(int i=0;i<103000;i++)dp[i] = 99; //dp 초기화
        for(int i=1;i<=5;i++)dp[arr[i]] = i; //dp[5] = 1, dp[55] = 2 ...
        
        
        for(int i : arr){
            if(i ==0)continue; //0은 범위가 아님
            for(int j = 1;j<=4;j++){
                if(i + arr[j] <103000)
                    dp[i+arr[j]] = Math.min(dp[i + arr[j]], dp[i] + j);
                if(i - arr[j] >= 1)
                    dp[i-arr[j]] = Math.min(dp[i - arr[j]], dp[i] + j);
                if(i * arr[j] < 103000)
                    dp[i * arr[j]] = Math.min(dp[i * arr[j]], dp[i] + j);
                if(i/arr[j] != 0)
                    dp[i / arr[j]] = Math.min(dp[i / arr[j]], dp[i] + j);
            }
        }
        int answer = dp[number];
        if(dp[number]>8)answer = -1;
        return answer;
    }
}

하지만 틀렸다!

일단 dp의 범위를 어디까지 돌려야 할지 몰랐다. 최대 number는 32000인데 더 큰수에서 나눗셈이나 뺄셈을 해도 32000이 나올 수 

있기 때문에 어디까지 돌려야 할지 감이 오지 않았다. 

 

따라서 다른 DP 방식을 알아보았다.

즉, 횟수를 기준으로 DP를 설정하는 것이다.

N을 1번 활용한 수 : N

N을 2번 활용한 수 : (N + N), (N - N), (N  * N), (N / N), NN

N을 3번 활용한 수: N + (N + N), N + (N - N), ...(N + N) + N, (N - N) - N, (N + N) * N, .....NNN

이러한 방식으로 N을 1번 사용한 수 집합, N을 2번 사용한 수 집합, N을 3번 사용한 수 집합, ...N을 8번 사용한 수 집합을 구해

1 ~ 8 까지 돌면서 number가 있는 집합을 return 해주면 된다.

 

집합을 구현할 때는 Set를 활용하였다. 중복처리에도 편하기 때문이다.

List<Set<Integer>>countList = new ArrayList<>();
for(int i=0;i<9;i++) 
   countList.add(new HashSet<>());

먼저 List로 전체 Set를 아우르는 List를 만들고, 각각의 인덱스에 Set 객체를 만든다.

countList.get(1).add(N); // 1개 쓴 값은 N 혼자
if(number == N)return 1;

일단 N을 1번째 사용한 집합에 N을 넣어준다. 당연한 것이다. 이것은 1개 사용했으니까 N 그대로 이다.

우리가 찾으려는 number가 N이면 1을 return 해주면 된다.

for(int i = 2;i<9;i++){
            Set<Integer>countSet = countList.get(i);
            
            
            //이전 통들을 가지고 경우의 수 찾기
            //ex) 3번통에 들어갈 숫자를 찾으려면
            //3번 통 = (1번통 =>연산 2번통), (2번통 =>연산 1번통))
            //괄호 때문
            for(int j = 1;j<i; j++){
                Set<Integer>pre = countList.get(j);
                Set<Integer>post = countList.get(i-j);
                
                for(int x : pre){
                    for(int y : post){
                        countSet.add(x+y);
                        countSet.add(x-y);
                        countSet.add(x*y);
                        if(x!=0 && y!= 0)countSet.add(x/y);
                    }
                }
            }
            // 마지막에 연속된 수 넣기 ex) N = 5이고 i =3이면 555넣기
            countSet.add(Integer.parseInt(String.valueOf(N).repeat(i)));
}

이제 N을 2번 사용한 집합 부터 순회 하면서 해당 집합에 해당하는 수를 넣어주면 된다.

for(int j = 1;j<i; j++){
                Set<Integer>pre = countList.get(j);
                Set<Integer>post = countList.get(i-j);
                
                for(int x : pre){
                    for(int y : post){
                        countSet.add(x+y);
                        countSet.add(x-y);
                        countSet.add(x*y);
                        if(x!=0 && y!= 0)countSet.add(x/y);
                    }
                }
}

이 부분이 이해가 안갈 수 있는데

예를 들어 N을 2번 사용한 집합은

N을 1번 사용한 집합 ----> 사칙연산 ----> N을 1번 사용한 집합

이다.

 

예를 들어 N을 3번 사용한 집합은

N을 1번 사용한 집합 ---> 사칙 연산(+-*/)------> N을 2번 사용한 집합

N을 2번 사용한 집합 ---> 사칙 연산(+-*/)------> N을 1번 사용한 집합

이다.

 

예를 들어 N을 4번 사용한 집합은

N을 1번 사용한 집합 ---> 사칙연산 ----> N을 3번 사용한 집합

N을 2번 사용한 집합 ---> 사칙연산 ----> N을 2번 사용한 집합

N을 3번 사용한 집합 ---> 사칙연산 ----> N을 1번 사용한 집합

이다.

 

간단하다. 순서 때문이다. 5 / (5 + 5) 랑 (5 + 5) / 5는 다르기 때문이다.

어차피 중복이 되어도 Set이 걸러주기 때문에 상관없다.

for(Set<Integer> sub : countList){
                if(sub.contains(number))
                    return countList.indexOf(sub);
 }
        
        return -1;

마지막에 N을 i번 사용한 집합을 순회 하면서 number가 있는지 찾는 것이다. 

number를 찾으면 i를 return 해주고 그렇지 않으면 -1를 return 한다.

---

전체 코드이다.

import java.util.*;
class Solution {
    public int solution(int N, int number) {
        List<Set<Integer>>countList = new ArrayList<>();
        for(int i=0;i<9;i++) 
            countList.add(new HashSet<>());
        
        countList.get(1).add(N); // 1개 쓴 값은 N 혼자
        if(number == N)return 1;
        
        for(int i = 2;i<9;i++){
            Set<Integer>countSet = countList.get(i);
            
            
            //이전 통들을 가지고 경우의 수 찾기
            //ex) 3번통에 들어갈 숫자를 찾으려면
            //3번 통 = (1번통 =>연산 2번통), (2번통 =>연산 1번통))
            //괄호 때문
            for(int j = 1;j<i; j++){
                Set<Integer>pre = countList.get(j);
                Set<Integer>post = countList.get(i-j);
                
                for(int x : pre){
                    for(int y : post){
                        countSet.add(x+y);
                        countSet.add(x-y);
                        countSet.add(x*y);
                        if(x!=0 && y!= 0)countSet.add(x/y);
                    }
                }
            }
            countSet.add(Integer.parseInt(String.valueOf(N).repeat(i)));// 마지막에 연속된 수 넣기 ex) N = 5이고 i =3이면 555넣기
        }
        for(Set<Integer> sub : countList){
                if(sub.contains(number))
                    return countList.indexOf(sub);
        }
        
        return -1;
    }
}