[프로그래머스] N으로 표현

programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - 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을 X번 사용하여 만들 수 있는 숫자들의 집합 hs[x] 를 선언했다.

 

hs[x] = N을 X번 사용하여 만들 수 있는 숫자들의 집합. ( 중복 X )

 

x = 1 일 경우,

hs[1] = N 하나만 존재한다.

 

x = 2 일 경우,

hs[2] = N을 2번 이어붙인 숫자 U

          N을 1번 사용해서 만들 수 있는 숫자와, N을 1번 사용해서 만들 수 있는 숫자 간의 사칙연산 값들

 

x = 3 일 경우,

hs[3] = N을 3번 이어붙인 숫자 U

          N을 1번 사용해서 만들 수 있는 숫자와, N을 2번 사용해서 만들 수 있는 숫자의 사칙연산 값 U

          N을 2번 사용해서 만들 수 있는 숫자와, N을 1번 사용해서 만들 수 있는 숫자의 사칙연산 값

 

x = 4 일 경우,

hs[4] = N을 4번 이어붙인 숫자 U

          N을 1번 사용해서 만들 수 있는 숫자와, N을 3번 사용해서 만들 수 있는 숫자의 사칙연산 값 U

          N을 2번 사용해서 만들 수 있는 숫자와, N을 2번 사용해서 만들 수 있는 숫자의 사칙연산 값 U

          N을 3번 사용해서 만들 수 있는 숫자와, N을 1번 사용해서 만들 수 있는 숫자의 사칙연산 값

 

.....

위와 같은 예시를 통해, 아래와 같은 규칙을 뽑아낼 수 있다.

 

x = y 일 경우,

hs[y] = N을 y번 이어붙인 숫자 U

          N을 1번 사용해서 만들 수 있는 숫자와, N을 (y-1)번 사용해서 만들 수 있는 숫자의 사칙연산 값 U

          N을 2번 사용해서 만들 수 있는 숫자와, N을 (y-2)번 사용해서 만들 수 있는 숫자의 사칙연산 값 U

           .....

          N을 (y-2)번 사용해서 만들 수 있는 숫자와, N을 2번 사용해서 만들 수 있는 숫자의 사칙연산 값 U

          N을 (y-1)번 사용해서 만들 수 있는 숫자와, N을 1번 사용해서 만들 수 있는 숫자의 사칙연산 값

 

이를 코드로 구현하여 문제를 해결하였다.

 

import java.util.*;

class Solution {
    
    public int sticky(int n, int times){
        String tmp = String.valueOf(n);
        
        for(int i=0; i<times - 1; i++){
            tmp += String.valueOf(n);
        }
        
        return Integer.valueOf(tmp);
    }
    
    public int solution(int N, int number) {

        int answer = -1;
        
        // HashSet[x] = N을 x번 사용해서 만들 수 있는 수들의 집합
        HashSet<Integer> hs[] = new HashSet[9];
        
        for(int i=0; i<9; i++){
            hs[i] = new HashSet<Integer>();
        }
        
        hs[1].add(N);
        
        for(int i=2; i<9; i++){
            hs[i].add(sticky(N, i)); // N을 i번 붙인 수 추가
            for(int j=1; j<i; j++){
                for(int a : hs[j]){
                    for(int b : hs[i-j]){
                        hs[i].add(a+b);
                        if(a>b){hs[i].add(a-b);};
                        hs[i].add(a*b);
                        if(a/b != 0){hs[i].add(a/b);};
                    }
                }
                
            }
        }
        
        for(int i=1; i<9; i++){
            if(hs[i].contains(number)){
                answer = i;
                break;
            }
        }
        
        return answer;
    }
}