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

문제

프로그래머스-N으로 표현
주어진 숫자 number를 N과 사칙연산으로 표현할 때 N의 사용횟수의 최소를 구하는 문제

• 제한 사항
  N : 1 <= N <= 9
  주어지는 숫자 : 1 <= number <=32,000
  수식에는 괄호와 사칙연산만 가능하며, 나누기 연산에서 나머지는 무시한다
  최솟값이 8보다 크면 -1을 리턴한다

• 예시
  N = 5, number = 12의 경우, 아래같은 방법으로 표현이 가능하다
  12 = 5 + 5 + (5 / 5) + (5 / 5) : N 사용횟수 : 6개
  12 = 55 / 5 + 5 / 5 : N 사용횟수 : 5개
  12 = (55 + 5) / 5 : N 사용횟수 : 4개

4가 최소 사용횟수이므로 4가 정답

풀이

우선 N으로 만들 수 있는 기본적인 것들을 만들어서 객체(만든 숫자, N사용 횟수)를 base에 저장했다
N= 5일때 사용횟수가 8이 넘지않는 것들은 다음과 같다
base : (5, 1), (1, 2), (55, 2), (11, 3), (555, 3), (111, 4) ...

1, 11 은 (5/5), (55/5)를 괄호로 묶어서 먼저 계산된 것으로 자리수보다 1회 사용횟수가 많다
base는 사용횟수가 작은순으로 정렬해서 후에 사용횟수가 8회가 넘으면 base의 반복을 중단하게 되어있다

가장 처음의 값인 (0, 0)을 큐에 넣어준다
큐가 빌때까지 노드(curr)을 하나씩 뽑는다
해당 노드(curr)가 number와 같으면 답에 저장하고 반복문을 종료한다
number와 같지않으면 base에서 하나씩 돌면서 curr의 사용횟수 + base의 사용횟수를 확인한다
8이 넘으면 제한사항에 위배되므로 진행하지 않는다
8이 넘지않으면 curr의 숫자와 base의 숫자의 사칙연산(+, -, *, /)을 진행한다

이때 사칙연산의 결과의 값을 map에 저장해서 현재의 사용횟수와 비교한다
map에 결과값이 있고, map에 저장된 값보다 사용횟수가 작으면 map 값의 갱신 후 큐에 넣어준다
map에 저장된 값보다 크면 건너뛴다(pass)
map에 저장된 값이 없으면 새로 저장하고 큐에 넣어준다

예를들어 현재 값이 55(사용횟수 : 2), 베이스 차례 값이 5(사용 횟수 : 1) 이라면,
사용횟수의 총 합이 3이므로 8을 넘지않는다
사칙연산을 수행한다
55 + 5 = 60 (사용횟수 : 3)
55 - 5 = 50 (사용횟수 : 3) 55 * 5 = 275 (사용횟수 : 3)
55 / 5 = 11 (사용횟수 : 3) 연산 결과를 map에 추가하고, [60, 50, 275, 11]을 큐에 저장한다

이후 60의 차례에서 60 / 5를 했을 때 12가 나오고, 사용횟수는 4가 나오게 된다

소스코드

살짝 정신없이 짠 감이 없잖아 있음

import java.util.*;
class Solution {
static HashMap<Integer, Integer> map;
	static ArrayList<Num> base;
	static PriorityQueue<Num> pq;
	static int answer;
	static boolean flag = false;

	public int solution(int N, int number) {
		map = new HashMap<>(); // 숫자와 사용횟수를 저장하기 위함(값의 범위가 종잡을수없어서 map사용)
		base = new ArrayList<>(); // 기본적인 숫자가 들어갈 것
		pq = new PriorityQueue<>(); // 연산 대상 숫자들이 들어갈 것

		answer = 10;
		int tmp = N; // 5, 55, 555를 만들기 위한 변수
		int c = 1; // 사용횟수 카운터
		while (c < 9) { // 최대는 8이므로 8이전으로 제한
			if (c < 7)
				base.add(new Num(tmp / N, c + 1)); // 1, 11, 111을 추가
			base.add(new Num(tmp, c++)); // 5, 55, 555를 추가
			int v = (int) (Math.log10(tmp) + 1); // 자릿수
			tmp = (int) (Math.pow(10, v) * N + tmp);
		}
		// base를 사용횟수 적은순으로 정렬
		base.sort(new Comparator<Num>() {
			@Override
			public int compare(Num o1, Num o2) {
				return o1.cnt - o2.cnt;
			}
		});

		pq.add(new Num(0, 0)); // 처음 연산할 수
		while (!pq.isEmpty()) {
			Num curr = pq.poll(); 
			if (curr.cnt > answer || curr.cnt > 8) // 정답보다 크거나 8을 넘어가면 종료
				break;
			if (curr.num == number) {
				answer = curr.cnt; // 정답인 경우 갱신
				break;
			}
			// base순환해서 연산해줌
			for (int i = 0; i < base.size(); i++) {
				if (base.get(i).cnt + curr.cnt > 8)
					break;
				Num b = base.get(i);
				isPoss(curr.num + b.num, curr.cnt + b.cnt, number);
				if (curr.num - b.num >= 0) // 두 수의 차가 양수인 경우만 동작
					isPoss(curr.num - b.num, curr.cnt + b.cnt, number);
				if (curr.num > 1) // 0을곱하거나 1을 곱하게되면 제외
					isPoss(curr.num * b.num, curr.cnt + b.cnt, number);
				if (curr.num >= b.num) // 몫이 0이나오는것을 방지하기 위함
					isPoss(curr.num / b.num, curr.cnt + b.cnt, number);
			}

		}
		return answer > 8 ? -1 : answer; // 답이 8보다 크다? -1 출력
	}

	private void isPoss(int nums, int cnts, int number) {
		if (nums == number && cnts < 9)
			answer = Math.min(answer, cnts);
		if (map.containsKey(nums)) { // map에 저장된 수와 비교
			if (map.get(nums) > cnts)
				map.put(nums, cnts);
			else
				return;
		} else {
			map.put(nums, cnts);
		}

		pq.add(new Num(nums, cnts)); // 다음 연산 대상에 추가
	}
}

class Num implements Comparable<Num> {
	int num;
	int cnt;

	public Num(int num, int cnt) {
		this.num = num;
		this.cnt = cnt;
	}
	@Override
	public int compareTo(Num o) {
		if (this.cnt == o.cnt)
			return this.num - o.num;
		return this.cnt - o.cnt;
	}
}