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

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

2. 입력

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

3. 예제

N	number	return
5	12	4
2	11	3

4. 풀이

처음 문제를 보고 DP를 이용하여 문제를 풀면 될 거 같은 느낌이 들었습니다. 하지만 아무리 최소 개수 점화식을 도출하려고 해도 규칙이 전혀 보이지 않았습니다. 그래서 개수가 아닌 개수로 만들 수 있는 숫자를 이용하여 DP를 구성해 보았습니다.

 

N이라는 숫자 1개로 만들 수 있는 숫자는 N 자신만 존재합니다.

 

2개로 만든 수들을 알아보기 전에 2보다 작은 수들의 합으로 2를 만드는 경우를 살펴보도록 하겠습니다.

 

2의 경우는 어떤 것이 있을까요? 1 + 1로 표현하는 것이 전부입니다.

 

3의 경우는 어떤 것이 있을까요? 1 + 2, 2 + 1로 2가지 경우가 있습니다.

 

4의 경우는 어떤 것이 있을까요? 1 + 3, 2 + 2, 3 + 1로 3가지 경우가 있습니다.

 

추가적으로 1 + 2, 와 2 + 1은 동일한 것이 아닌가라는 생각을 할 수 있습니다. 하지만 서로 다른 값입니다.

 

2라는 의미는 괄호를 통한 계산 결과와 동일하기 때문입니다.

 

예로 들어 8 - (8 + 8)과 (8 + 8) - 8은 서로 다른 결과 값이 됩니다.

 

자 그럼 N숫자 2개로 만들 수 있는 숫자는 1개로 만든 숫자 (+, -, *, /) 1개로 만든 숫자가 될 것입니다.

 

여기서 N숫자를 연속한 값 또한 N을 2개 사용하여 만들 수 있는 숫자로 판단하기 때문에 N을 2개 붙여 만들어지는 숫자도 추가하여 줍니다.

 

N숫자 3개로 만들 수 있는 숫자는 1개로 만든 숫자 (+, -, *, /) 2개로 만든 숫자, 2개로 만든 숫자 (+, -, *, /) 1개로 만든 숫자가 될 것입니다.

 

여기서 N숫자를 연속한 값 또한 N을 3개 사용하여 만들 수 있는 숫자로 판단하기 때문에 N을 3개 붙여 만들어지는 숫자도 추가하여 줍니다.

 

N숫자 4개로 만들 수 있는 숫자는 1개로 만든 숫자 (+, -, *, /) 3개로 만든 숫자, 2개로 만든 숫자 (+, -, *, /) 2개로 만든 숫자, 3개로 만든 숫자 (+, -, *, /) 1개로 만든 숫자가 될 것입니다.

 

이제 만들어진 1 ~ 8까지 개수를 가지고 있는 통에서 찾는 수가 있는 최소의 통을 찾아 해당 통에 적혀 있는 개수를 반환하면 문제를 풀 수 있습니다.

 

5. 코드

전체 코드는 Git에 있습니다.

List<Set<Integer>> countList = new ArrayList<>();

for(int i=0; i<9; i++)
	countList.add(new HashSet<>());

countList.get(1).add(N); // N을 1개 쓴 값은 N 혼자이다.

for(int i=2; i<9; i++){
	Set<Integer> countSet = countList.get(i);

	for(int j=1; j<=i; j++){
		Set<Integer> preSet = countList.get(j);
		Set<Integer> postSet = countList.get(i - j);

		for(int preNum : preSet){
			for(int postNum : postSet){
				countSet.add(preNum + postNum);
				countSet.add(preNum - postNum);
				countSet.add(preNum * postNum);

				if(preNum != 0 && postNum != 0)
					countSet.add(preNum / postNum);
			}
		}
	}

	countSet.add(Integer.parseInt(String.valueOf(N).repeat(i)));
}

for(Set<Integer> sub : countList){
	if(sub.contains(number))
		return countList.indexOf(sub);
}

return -1;