[프로그래머스] 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 하라고 했으므로 경우의 수가 그렇게 크게 나지 않는다.

 

일단 HashSet 을 9가지 배열로 만들어 준다.

1 ~ 8 개의 숫자를 사용했을 경우의 모든 수를 저장하기 위함이다.

 

초기 set[i] 값에

1 -> N

2 -> 10N + N

3 -> (10N + N) * 10 + N

...

와 같이 값을 미리 넣어준다.

5, 55, 555, 5555, 55555, 555555 와 같은 수는 사칙연산으로 만들 수 없는 수기 때문이다.

 

그런 뒤 1 ~ 8 까지의 배열의 HashSet에 있는 값을 하나씩 구성해준다.

        for(int i = 1; i < 9 ; i++){
            for(int j = 1; j < i ; j++){
                for(int a : set[j]){
                    for(int b : set[i - j]){
                        if(a - b > 0)
                            set[i].add(a - b);
                        if( b - a > 0)
                            set[i].add(b - a);    
                        set[i].add(a + b);
                        set[i].add(a * b);                      
                        if( b != 0)
                            set[i].add(a / b);
                        
                        if( a != 0)
                            set[i].add(b / a);
                    }
                }
            }
        } 

 

위 코드가 구성하는 코드다. set[j] 의 수와 set[i - j] 의 수를 합친값을 set[i]에 넣어 준다.

set[j] 는 j 개 N을 사용한 수, set[i -j] 는 i - j 개 N을 사용한 수기 때문에 두 값을 연산하면 N을 i 개 쓴 값이 나온다.

 

 

이렇게 모든 계산 값을 구한 뒤 해당 값이 있으면 return 하고 아니면 -1을 return 해주면 된다.

 

<전체코드>

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        int answer = -1;
        
        HashSet<Integer>[] set = new HashSet[9];
        
        int countN = N;
        for(int i = 1; i < 9 ; i++){
            set[i] = new HashSet<Integer>();
            
            set[i].add(countN);
            countN = countN * 10 + N;
        }
        
        for(int i = 1; i < 9 ; i++){
            for(int j = 1; j < i ; j++){
                for(int a : set[j]){
                    for(int b : set[i - j]){
                        if(a - b > 0)
                            set[i].add(a - b);
                        if( b - a > 0)
                            set[i].add(b - a);    
                        set[i].add(a + b);
                        set[i].add(a * b);                      
                        if( b != 0)
                            set[i].add(a / b);
                        
                        if( a != 0)
                            set[i].add(b / a);
                    }
                }
            }
        } 
        
        for(int i = 1 ; i < 9 ; i++){
            if(set[i].contains(number)){
                return i;
            }
        }
        
        return answer;
    }
}