프로그래머스 - N으로 표현

문제 설명

---

N에 대한 사칙연산으로 number를 만들 수 있는 최소 N의 사용개수를 구하는 문제이다.

n의 사용횟수에 따라 값을 저장한다.

하지만 아래 방식처럼 알고리즘을 작성하면 “12 = (55 + 5) / 5” 해당식에서 나타난 괄호에 대한 우선순위 적용이 안되어있어 최소 개수를 구할 수 가 없다.

왜냐하면 괄호 연산에 따라 값이 달라지기 때문이다. := 사칙연산은 우선순위가 존재하므로

“4+4*4“ 의 식이 주어질때 20으로 계산된다. 하지만 괄호가 들어간 (4+4) * 4 식으로 바꾸면 32가 나오듯이 괄호에 따라 중간 결과값이 달라지는 경우가 많아 해당 괄호도 있도록 알고리즘을 구성해야 한다.

괄호가 있도록 구성하기 위해 n이라는 숫자를 4번 사용하여 만드는 경우의 수를 구할떄 n을 3번 사용한 경우와 n을 1번 사용한 경우의 수를 조합하여 결과값을 도출한다.

예를 들어 n=4이고 number가 17일때, 밑의 경우가 최소의 개수를 사용하여 만든 개수이다.

이처럼 n을 i번 n을 4-i번 사용한것들을 조합하면 괄호연산을 적용한 것처럼 나오게 된다.

풀이

---

public int solution(int N, int number) {
        int answer = 0;
        Set<Integer> dp[]=new Set[9];
        
        if(N==number){
            return 1;
        }
        
        dp[1]=Set.of(N);
        
        for(int i=1; i<=8; i++){
            dp[i]=new HashSet<>();
            String val=String.valueOf(N).repeat(i);
            dp[i].add(Integer.parseInt(val));
        }
        
        for(int cnt=2; cnt<=8; cnt++){
            // 이전 마이그레이션
            for(int i=1; i<cnt; i++){
                for(int a: dp[i]){
                    for(int b: dp[cnt-i]){
                        dp[cnt].add(a+b);
                        dp[cnt].add(a-b);
                        dp[cnt].add(a*b);
                        if(a!=0 && b!=0){
                            dp[cnt].add(a/b);    
                        }
                    }
                }
            }
            
            if(dp[cnt].contains(number)){
                return cnt;
            }
            
        }
        
        return -1;
    }

public int solution(int N, int number) {
        int answer = 0;
        Set<Integer> dp[]=new Set[9];
        
        if(N==number){
            return 1;
        }
        
        dp[1]=Set.of(N);
        
        for(int i=1; i<=8; i++){
            dp[i]=new HashSet<>();
            String val=String.valueOf(N).repeat(i);
            dp[i].add(Integer.parseInt(val));
        }
        
        for(int cnt=2; cnt<=8; cnt++){
            // 이전 마이그레이션
            for(int i=1; i<cnt; i++){
                for(int a: dp[i]){
                    for(int b: dp[cnt-i]){
                        dp[cnt].add(a+b);
                        dp[cnt].add(a-b);
                        dp[cnt].add(a*b);
                        if(a!=0 && b!=0){
                            dp[cnt].add(a/b);    
                        }
                    }
                }
            }
            
            if(dp[cnt].contains(number)){
                return cnt;
            }
            
        }
        
        return -1;
    }