N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return. 이때 최소값이 8보다 크면 -1을 return

숫자 i개를 사용했을 때 만들어지는 모든 수를 하나의 통에 담는다.

• i=1 : 숫자 1개로 만들 수 있는 값 → N
• i=2 : 숫자 2개로 만들 수 있는 값 → (i=1값) +-*/ (i=1값), NN
• i=3 : 숫자 3개로 만들 수 있는 갓 → (i=1값) +-/ (i=2값), (i=2값) +-/ (i=1값), NNN
• … i=8까지 탐색 (제약 조건에 8이상이면 -1을 return)

※ -, /의 경우 (1-2) ≠ (2-1) 이므로 순서를 고려해야 한다.

우선 통을 저장하기 위한 list를 만들고 HashSet(통)을 요소로 저장한다. (List<HashSet<Integer>> list)

→ list.get(i).add() 하면 i번째 요소에 있는 집합에 값을 저장 가능

→ i번째 통에는 가능한 경우를 사칙연산한 결과와 N을 i번 반복한 값을 저장한다.

※ N을 i번 반복하기 위한 간단한 메서드 repeat(i) 사용

풀이 코드

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        
        //통 만들기
        List<HashSet<Integer>> list = new ArrayList<>();
        
        //8개의 통 만들기
        for(int i=0; i<=8; i++) {
            list.add(new HashSet<Integer>());
        }
        
        //i=1인 경우부터 시작
        list.get(1).add(N);
        if(number == N) return 1;
        
        //i=2 ~
        for(int i=2; i<=8; i++) {
            HashSet<Integer> tmp = list.get(i);
            
            //이전 i값에서 현재 i값 만들기
            for(int j=1; j<i; j++) {
                HashSet<Integer> a = list.get(j);
                HashSet<Integer> b = list.get(i-j);
                
                for(int x : a) {
                    for(int y : b) {
                        tmp.add(x + y); // 더하기
                        tmp.add(x - y); // 빼기
                        tmp.add(x * y); // 곱하기
                        if(x != 0 && y != 0) tmp.add(x / y); // 나누기
                    }
                }
                tmp.add(Integer.parseInt(String.valueOf(N).repeat(i)));
            }
            
            // i개의 N으로 number를 만들 수 있다면 끝
            if(tmp.contains(number)) return i;
        }
        
        // 8개보다 더 많은 숫자가 필요하므로 -1
        return -1; 
    }
}