[Programmers] N으로 표현 (Java)

1.  문제 링크

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

2.  문제

아래와 같이 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 함수를 작성하세요.

3.  제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

4.  소스코드

import java.util.*;

class Solution {
    static HashSet<Integer>[] lists;
	public static int solution(int N, int number) {
        if(N == number) return 1;
		int answer = 0;
		lists = new HashSet[9];
		for(int index = 0; index < 9; index++) lists[index] = new HashSet<>();
		lists[1].add(N);
		for(int size = 2; size <= 8; size++) {
			for(int first = 1; first <= size / 2; first++) {
				calcEachCase(size, first, size - first);
				calcEachCase(size, size - first, first);
			}
			String n = Integer.toString(N);
			lists[size].add(Integer.parseInt(n.repeat(size)));
			if(lists[size].contains(number)) {
				answer = size;
				break;
			}
		}
		return answer == 0 ? -1 : answer;
	}
	
	static void calcEachCase(int size, int first, int second) {
		for(int n1 : lists[first]) {
			for(int n2 : lists[second]) {
				lists[size].add(n1 + n2);
				lists[size].add(n1 - n2);
				lists[size].add(n1 * n2);
				try {
					lists[size].add(n1 / n2);
				} catch(Exception e) {}
			}
		}
	}
}