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

오랫만에 알고리즘 문제 풀이를 적어보겠습니다~

DP는 풀면 풀수록 어려운데, 특히 이번 문제는 생각치도 못했던 방법이어서 안잊도록 적어보려해요!

오늘의 문제는 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과 사친연산으로 number를 구성했을 때 N의 최소갯수를 구한다.

풀이방법

처음에는 문제를 읽고... 옳다구나! 그냥 앞에서부터 사칙연산을 골라서 모든 경우의 수를 다 계산하면되겠다!해서

이렇게 설계했습니다. 테스트케이스도 정답이 맞게 나왔구요..

[이 설계대로 짠 잘못된 코드]

public class Programmers_N으로표현 {
    static int min;
    
	public static int solution(int N, int number) {
		// 최소값을 저장할 변수
		min = 9;
		// N 사용 횟수의 최솟값을 찾음
		find(0, 0, N, number);
		// min이 9이상이면 -1을 반환
		return min > 8 ? -1 : min;
	}

	private static void find(int sum, int cnt, int N, int number) {
		// cnt가 9이상이면 더 갈 필요가 없다
		if (cnt > 8) {
			return;
		}
		// 찾는 숫자와 계산 값이 같으면 최솟값인지 비교하고 저장
		if (sum == number) {
			min = Math.min(min, cnt);
			return;
		}
		// N부터 넣어보고 NN, NNN, ...으로 계산을 시도
		int num = N;
		for (int i = 1; i < 9; i++) {
			// 더하기
			find(sum + num, cnt + i, N, number);
			// 빼기
			find(sum - num, cnt + i, N, number);
			// 나누기
			find(sum / num, cnt + i, N, number);
			// 곱하기
			find(sum * num, cnt + i, N, number);
			// num을 다음 자리 숫자로 만듬
			num = num * 10 + N;
		}
	}
}

그런데 예외사항이 있었습니다. 앞에서 부터 계산을 하게되다보니 뒤순서가 우선인 계산(뒤에있는 곱하기나 나눗셈, 괄호 등)을 전혀 생각 못했던 것이죠!

N	number	answer	내 설계의 답
5	26	4	5

=> 앞에서부터 계산을 하다보니 5*5+5/5를 (5*5+5)/5로 계산해서 이것은 답이 아니고, (5*5*5+5)/5이게 답이다! 라고 판단을 해버린 것이었죠..

 

그래서 생각을 다시 했습니다. 뒷 계산에 해당되는 작은 계산부터 미리 구해 놓는 방식으로요!

N의 개수; f(N)		+	-	*	/
1; f(1)	5
2; f(2)	55	f(1)+f(1) =5+5=10	f(1)-f(1) =5-5=0	f(1)*f(1) =5*5=25	f(1)/f(1) =5/5=1
3; f(3)	555	f(1)+f(2) f(2)+f(1)	f(1)-f(2) f(2)-f(1)	f(1)*f(2) f(2)*f(1)	f(1)/f(2) f(2)/f(1)
4; f(4)	5555	f(1)+f(3) f(2)+f(2) f(3)+f(1)	f(1)-f(3) f(2)-f(2) f(3)-f(1)	f(1)*f(3) f(2)*f(2) f(3)*f(1)	f(1)/f(3) f(2)/f(2) f(3)/f(1)

f(1)+f(2)와 f(2)+f(1)처럼 중복이 발생하지않게 Set으로 N=n일때 가능한 경우의 수를 모두 저장해서 DP방식으로 풀었습니다.

 

코드

import java.util.HashSet;

public class Programmers_N으로표현 {
	public static void main(String[] args) {
		int N = 5;
		int number = 26;
		System.out.println(solution(N, number));
	}

	public static int solution(int N, int number) {
		// N을 1~8개 사용했을 때의 모든 숫자를 저장할  set
		HashSet<Integer>[] numberSet = new HashSet[9];
		// N, NN, NNN, ...을 만들기 위한 변수
		int num = N;
		// 1~8의 hashset을 초기화하고, 초기값을 넣어줌
		for (int i = 1; i < 9; i++) {
			numberSet[i] = new HashSet<Integer>();
			numberSet[i].add(num);
			num = num * 10 + N;
		}
		// N을 1~8번 사용했을 때
		for (int i = 1; i < 9; i++) {
			// N을 1~8번 사용한 것과 1~i번 사용한 것을 연산했을 때
			for (int j = 1; j < i; j++) {
				// j번 사용
				for (int num1 : numberSet[j]) {
					// num1+num2에 사용된 N의 개수가 i이어야 하므로 i-j번째에 있는 수
					for (int num2 : numberSet[i - j]) {
						numberSet[i].add(num1 + num2);
						numberSet[i].add(num1 - num2);
						numberSet[i].add(num1 * num2);
						// 나눗셈에서 나누는 숫자가 0이 될 수 없다
						if (num2 != 0) {
							numberSet[i].add(num1 / num2);
						}
					}
				}
			}
		}
		int answer = -1;
		// 최솟값을 찾는 것이므로 1부터
		for (int i = 1; i < numberSet.length; i++) {
			// 해당하는 숫자가 있으면 N을 i번 사용한 것
			if (numberSet[i].contains(number)) {
				answer = i;
				break;
			}
		}
		return answer;
	}
}