[프로그래머스/JAVA] N으로 표현 - 동적계획법(Dynamic Programming)

 

[2021-07-05]

 

전직장 동기와 오붓하게 알고리즘 스터디를 하며

매주 문제를 풀고 있지만 점점 공부하는게 많아지니(ㅋㅋㅋㅋ)

블로그를 소홀히 하게 됐다,,, 열심히 올려야 하는데..!!

올리고 싶은게 넘 많은데 의지에 비해 몸이 안따라준다 희희

오늘 푼건 알고리즘 문제 중에서도 가장 Hate하는 동적 계획법^^이라

어렵기도 하고 까먹기 전에 포스팅을 해야 해서 올린다

 

 

---

 

코딩테스트 연습 - 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	return
5	12	4
2	11	3

 

입출력 예 설명

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

 

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

 

 

풀이

 

사실 동적 계획법은 아직도 잘 감이 안온다

개념을 좀더 빠삭하게 익히고 했으면 더 좋았으려나ㅠ

 

일단 문제는 2차원 배열 혹은 2차원 Collection 구조를 사용해서 N으로 만들 수 있는 결과 값들을 넣어 두는 방식으로 풀었다. 결과 값은 NN, N, NNN과 같이 N의 조합으로 만들어지는 숫자와, (현재 N의 갯수-1)개가 사용된 배열에서 N을 사칙연산 해준 값을 저장해 마지막에 찾는 방식으로 풀었다. 

 

기본적으로 생각한 알고리즘은 위와 같은데, 풀다보니 고려하지 못한 여러 문제들이 있었다.ㅎㅎ

 

 

1. 항의 조합(괄호항)

초기 풀이 방식

 

그림은 2차원 배열처럼 보이지만 실제론 N이 사용 된 개수에 따라 결과 값의 개수 또한 달라지기에 동적 크기를 갖는 Collection을 사용했다. 여기까진 초기에 생각한 구조를 그대로 옮긴 정도라 그렇게 오래걸리지 않았는데, 허점이 많기에 당연히 통과하지 못한다. (그래도 의외인건 제출 전 테스트 케이스 2개는 통과함,, Why,,?)

 

결과 > 테스트 케이스 1, 5, 6, 7, 8 실패
실패의 원인은 항의 조합(괄호항)을 고려하지 않아서 틀린거라 유추했다. 위 방식은 (1개, N-1개)로 구성된 식의 결과 값만 얻어지는데, 앞/뒤 항의 위치에 따라 결과 값이 달라지는 곱하기(*)와 나눗셈(/)의 특성을 고려하면 (1개, N-1개), (2개, N-2개), (3개, N-3개) 등 항이 다양하게 구성된 식의 결과 값도 도출 해야한다.

(좌) 이전 방식의 결과 값 / (우) 변경하려는 방식의 결과 값 

 

 

2. 중복

두번째는 중복이다. 초반엔 단순히 ArrayList를 사용하다가 중복에 대한 처리가 필요하다고 생각되어, Set으로 바꿨다. 아무래도 문제에서 요구하는 최종 값이 number를 만들기 위해 필요한 N의 갯수이기 때문에, 생성된 List에서 number을 찾아야 한다. 찾는 과정에서 성능 및 효율을 고려하면 중복 제거가 필수적이다. 

 

 

최종 코드

ArrayList<HashSet<Integer>> list = new ArrayList<HashSet<Integer>>();
        
// 배열 만들기
for (int i = 0; i < 9; i++) { // 최소값이 8보다 크면 -1 리턴 하면됨(범위는 8개까지)
	list.add(new HashSet<Integer>());
}

HashSet<Integer> currentList;
HashSet<Integer> leftList;
HashSet<Integer> rightList;

list.get(1).add(N);

for(int i=2 ; i<9 ; i++) {
	currentList = list.get(i);

	for(int j=1 ; j <= i ; j++) {
		leftList = list.get(j);		
		rightList = list.get(i-j);

		for(int leftNum : leftList) {
			for(int rightNum : rightList) {
				currentList.add(leftNum + rightNum);
				currentList.add(leftNum - rightNum);
				currentList.add(leftNum * rightNum);

				if(leftNum != 0 && rightNum != 0) {
					currentList.add(leftNum / rightNum);
				}
			}
		}
	}
			
	// 55, 555와 같은 숫자 만들어주기
	int sum = 0;
	for(int k=0 ; k<i ; k++) {
		sum += N * Math.pow(10, k);
	}
	currentList.add(sum);
            
}
		
int answer = -1;
for (int i = 1; i < list.size(); i++) {
	currentList = list.get(i);
	if(currentList.contains(number)) {
		answer = i;
		break;
	}			
}
		
return answer;

 

사실 이렇게 푼 코드도 마음에 안든다,,,, 너무 마음에 안든다,,,!

더 좋은 코드가 있을텐데 동적 계획법은 아직 문제 풀기에도 벅차기에,,ㅎ,ㅎㅎ

더 열심히 공부해야겠다😂😂 

 

---