[프로그래머스 : 레벨3] N으로 표현 : Dynamic Programing

이번 문제도 풀다가 도저히 감이 잡히질 않아서 답을 검색했다.

 

이번 문제는 풀이를 봐도 쉽게 이해가 가질 않았는데 손코딩 + 디버깅을 하니까 이해가 갔다.

(자바 이클립스 디버깅에 대해 잘 모르는 사람은 아래 링크 참고하면 될것 같다.)

https://wpioneer.tistory.com/92

[Java] 이클립스 디버깅 하는 방법

 

일단 그럼 문제부터 보자.

 

문제 설명

 

아래와 같이 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	return
5	12	4
2	11	3

 

입출력 예 설명

 

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

내가 본 풀이는 아래와 같다.

public class PreTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		PreTest p = new PreTest();
		int n = 5;
		int number = 12;
		System.out.println(p.solution(n, number));

	}

	public int solution(int N, int number) {
		int answer = 0;
		//Set을 담을수 있는 배열을 setArr을 만듬
		Set<Integer>[] setArr = new Set[9];
		int t = N;
		//근데 0부터 채우지 않음
		for (int i = 1; i < 9; i++) {
			//HashSet 만들고
			setArr[i] = new HashSet<>();
			//해당 set에다가 t의 값을 더함
			setArr[i].add(t);
			//N이 5라고 하면 55를 T로 설정
			//그래서 이게 9번째 자리까지 만듬 
			//ex ) 5,55,555,5555,55555,555555
			t = t * 10 + N;
		}
		
		for(int i = 0; i<9; i++) {
			System.out.println(setArr[i]);
		}
		
		for (int i = 1; i < 9; i++) {
			for (int j = 1; j < i; j++) {
				for (int a : setArr[j]) {
					for (int b : setArr[i - j]) {
						System.out.println("a : "+ a + " b : "+b);
						setArr[i].add(a + b);
						setArr[i].add(a - b);
						setArr[i].add(b - a);
						setArr[i].add(a * b);
						if (b != 0) {
							setArr[i].add(a / b);
						}
						if (a != 0) {
							setArr[i].add(b / a);
						}
					}
					System.out.println("setArr["+i+"] : "+setArr[i]);
				}
				System.out.println("setArr["+i+"] : "+setArr[i]);
			}
		}
		
		for (int i = 1; i < 9; i++) {
			System.out.println(setArr[i]);
			if (setArr[i].contains(number)) {
				answer = i;
				break;
			}
		}
		return answer;
	}

}

 

위 소스를 실행시켜보면 일단 

 

setArr[0] = null

setArr[1] = 5

setArr[2] = 55

setArr[3] = 555

setArr[4] = 5555

setArr[5] = 55555

setArr[6] = 555555

setArr[7] = 5555555

setArr[8] = 55555555

 

이렇게 setArr을 초기화 한다.

 

근데 왜 0의 자리에는 값을 집어 넣지 않냐 라는 의문을 가질수가 있다.

왜냐면 내가 그랬기 때문이다.

 

0의 자리에 값을 집어넣지 않은 이유는

5와 5의 사칙연산을 하지 못하고 5와 55의 사칙연산부터 시작하기때문이다.

 

그럼 위의 소스를 설명을 하자면 위 소스는 

5와 5의 사칙연산의 값인 [0, 1, 55, 25, 10] 를 setArr[2]에 저장하고

그다음엔 5와  [0, 1, 55, 25, 10]의 사칙연산인

[0, 2, -4, -5, 4, 5, 6, 555, 11, 15, -50, 50, 275, -20, 20, 60, 125, 30]를 setArr[3] 저장하고

이제 [0, 1, 55, 25, 10]과 5의 사칙연산의 값인

 [0, 2, -4, -5, 4, 5, 6, 555, 11, 15, -50, 50, 275, -20, 20, 60, 125, 30] 을

setArr[3]에 저장하는거다 위의 상황을 보면 알수 있듯이 각 자리수로 생기는 모든 값들을 저장하는것이다.

 

그래서 모든 값들을 배열에 저장하니 Dynamic하다고 볼수 있다.

그리고 문제풀면서 느낀거지만 모든 조합을 구하는거다 보니 bfs로 문제를 푸는 사람도 있었는데 

시간복잡도를 계산해본 결과 위와 같이 푸는게 시간복잡도가 제일 낮았다.

 

느낀점

1. 손코딩이 답이다.

2. 특정 값들을 일일히 더해서 원하는 결과가 나오는지 한번 돌려보자.