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. 풀이
숫자를 사용한 횟수를 구해야하는 문제입니다.
그리고 입력 제한에 사용한 횟수의 최소값이 1이고 최대값은 9라는 조건이 주어졌습니다.
N / N = 1 이기때문에 모든 수를 표현할 수 있지만, 최솟값이 8이 넘어가면 -1을 리턴하면 된다는 조건이 존재합니다.
문제를 보았을 때, 명확한 방법이 떠오르지 않기에 쉬운것 부터 해보겠습니다.
숫자를 사용한 횟수를 반환해야 하기때문에 숫자를 1개 쓰는 경우부터 시작해보겠습니다.
숫자 N이 하나라면 N만 표현할 수 있습니다.
N이 두개라면 다음과 같은 것들이 가능합니다.
NN
N + N
N - N
N * N
N / N
N을 이어붙인 것과 사칙연산이 해당됩니다.
그렇다면 3개는 어떨까요?
3개부터는 조금 복잡해집니다.
N + N + N
N + N - N
N + N * N
N + N / N
N - N + N
N - N - N
N - N * N
N - N / N
N * N + N
N * N - N
...
여기에 괄호까지 들어가면 엄청나게 많은 경우가 존재합니다.
그러나 모두 적진 않았지만 어느정도 유추는 가능합니다.
N하나로 표현할 수 있는 경우의 수는 N 하나
N 2개로 표현할 수 있는 경우의 수는 N 하나로 표현할 수 있는 경우에 사칙연산을 적용한 경우와 N 두개를 이어붙인 것
N 3개로 표현할 수 있는 경우의 수는 N 2개로 표현할 수 있는 경우에 N 하나로 표현할 수 있는 경우와 사칙연산을 적용한 경우와 N 3개를 이어붙인 것
이런식으로 표현할 수 있습니다.
하지만 괄호가 존재하기 때문에 반대의 경우도 고려해야합니다.
예를 들어 N이 5라고 가정해보겠습니다.
5 + (5 * 5) = 30
(5 + 5) * 5 = 50
이렇게 다르기 때문에,
N 하나로 표현할 수 있는 경우에 N 2개로 표현할 수 있는 경우를 따로 고려해야합니다.
5 + (5 * 5)는 N 1개로 표현할 수 있는 경우와 N 2개로 표현할 수 있는 경우를 더하기 연산한 결과이고,
(5 + 5) * 5 는 N 2개로 표현할 수 있는 경우와 N 1개로 표현할 수 있는 경우에 곱하기 연산을 적용한 결과입니다.
조금씩 규칙이 보이기 시작합니다.
임의의 숫자(제한 사항에 의해 1~8) x개로 표현할 수 있는 수들의 집합을 f(x)라고 하겠습니다.
그리고 N을 x개 연속 붙인 NNN이 하나 존재합니다.
그러면
f(3) = f(1)로 표현할 수 있는 수들의 집합과 f(2)로 표현할 수 있는 수들의 집합에 사칙연산을 적용한 결과
+
f(2)로 표현할 수 있는 수들의 집합과 f(1)로 표현할 수 있는 수들의 집합에 사칙연산을적용한결과
+
NNN
라고 표현할 수 있습니다.
사칙연산을 적용한 결과라고 하면 너무기니까 임의의 연산 ★이라고 하겠습니다.
정리하면, f(x) = f(x-1) ★ f(x-2) + f(x-2) ★ f(x-1) + NNN 입니다.
이렇게 정리하고 보니 조금 익숙한 형태가 보입니다.
동일한 작은 문제들이 반복하여 나타나고, 부분 문제의 최적 결과 값을 사용해 전체문제의 최적 결과를 낼 수 있는 문제.
이렇게 점화식의 형태로 표현할 수 있는 문제는 동적 프로그래밍을 통해 해결할 수 있습니다.
코드로 표현할 때 가장 중요하고 복잡한 부분은 ★연산을 정의하는 부분일 것 같습니다.
그래서 ★연산을 별도의 함수로 선언하고 그 나머지 부분을 먼저 구현해보겠습니다.
List<Set<Integer>> setList = new ArrayList<>();먼저, 'N으로 표현할 수 있는 수들의 집합'을 담기 위한 자료구조를 선언하겠습니다.
연산을 적용하다 보면 같은 값이 나오는 경우가 존재합니다.
위의 예에서 찾아보면 5 + (5 + 5) 와 (5 + 5) + 5 는 순서는 바뀌었지만 결과는 같습니다.
그래서 이런 경우를 제거해주기 위해서 Set 자료구조를 사용하겠습니다.
그리고 N을 1번 사용하는 경우부터 최대 8번까지 사용하는 경우까지의 자료구조를 담기 위해서 List 형태의 자료구조를 외곽에 선언해주었습니다.
JSON으로 표현하면 아래와 같은 구조가 될 것입니다.
[
[
5
],
[
55,
5 + 5,
5 - 5,
5 * 5,
5 / 5
],
[
5 + (5 + 5),
5 - (5 + 5),
5 * (5 + 5),
5 / (5 + 5),
...
],
]
근데 여기서 1개로 표현할 수 있는 자료구조는 매우 간단합니다.
그냥 N 자기자신만 표현이 가능하기 때문에, number 와 N이 같은 경우에는 바로 결과를 반환하겠습니다.
if(N == number) return 1;
for(int i=0; i<9; i++) {
setList.add(new HashSet<>());
}
setList.get(1).add(N);반환은 하더라도 다음 계산식에 연산이 사용되므로 setList의 1번 인덱스에 값을 넣어주었습니다.
for(int i=2; i<9; i++) {
for(int j=1; j < i; j++) {
unionSet(setList.get(i), setList.get(i-j), setList.get(j));
}
}
★연산의 구체적인 로직은 함수로 빼주고, 전체적인 구조를 잡기 위해
f(x) = f(x-1) ★ f(x-2) + f(x-2) ★ f(x-1)
를 코드로 표현한 내용입니다.
unionSet이 ★연산에 해당되고, setList의 i인덱스는 N을 i번 사용했을 때 표현할 수 있는 수들의 집합을 의미합니다.
이중 반복문안에서 j가 i-1 까지 증가하는 이유는 점화식에서 f(3) 은 f(1)과 f(2)로 표현이 가능하지만
f(5)같은 경우에는 f(1),f(4) 로 표현하는 방법과 f(2),f(3)으로 표현하는 방법이 존재하는 것처럼 여러개가 존재하는 경우가 있기 때문입니다.
그래서 j가 i까지 증가하면, i를 2개의 정수의 합연산으로 표현가능한 모든 경우를 표현할 수 있습니다.
i = i - j + j 와 같은 형태입니다.
| i = 5, j = 1 | i = 5, j = 2 | i = 5, j = 3 | i = 5, j = 4 |
| 5 = 1 + 4 | 5 = 2 + 3 | 5 = 3 + 2 | 5 + 4 + 1 |
f(1)은 숫자 N을 1개 써서 표현할 수 있는 수들의 집합
f(4)는 숫자 N을 4개 써서 표현할 수 있는 수들의 집합
이고, 괄호로 인해 반대의 경우도 고려해야 한다고 했으므로, f(1) ★ f(4) 와 f(4) ★ f(1)은 다르다고 했습니다.
그렇기 때문에 이렇게 표현할 수 있습니다.
그리고 여기에는 N을 i개 사용한 경우가 포함이 안되어 있으므로 포함시켜주도록 하겠습니다.
위에서 이야기한 NNN 의 경우입니다.
for(int i=2; i<9; i++) {
for(int j=1; j < i; j++) {
unionSet(setList.get(i), setList.get(i-j), setList.get(j));
}
String n = Integer.toString(N);
setList.get(i).add(Integer.parseInt(n.repeat(i)));
}
마지막으로, 만약 N을 i개 사용한 경우에 number를 표현할 수 있다면 i를 반환해줍니다.
i는 2부터 증가하기 때문에 2개로 표현할 수 있는 경우부터 체크해서 반환할 수 있습니다.
for(int i=2; i<9; i++) {
for(int j=1; j < i; j++) {
unionSet(setList.get(i), setList.get(i-j), setList.get(j));
}
String n = Integer.toString(N);
setList.get(i).add(Integer.parseInt(n.repeat(i)));
for(int num : setList.get(i)) {
if( num == number) return i;
}
}
return -1;그리고 i 가 8까지 증가했는데도 아직 number를 표현할 수 있는 경우가 setList안에 포함되어 있지 않다면 제한사항에 따라 -1을 반환해주면 됩니다.
그리고 아까 지나쳤던 ★의 구체적인 로직을 구현해 보겠습니다.
private void unionSet(Set<Integer> union,Set<Integer> aSet, Set<Integer> bSet) {
for(int a : aSet) {
for(int b : bSet) {
union.add(a + b);
union.add(a - b);
union.add(a * b);
if(b != 0) {
union.add(a / b);
}
}
}
}
비어있는 f(i) 에 f(i - j)과 f(j)의 원소들에 대해 사칙연산을 수행한 결과를 집어넣어주는 것입니다.
Set 자료구조이기 때문에 중복된 결과가 나와도 괜찮습니다. 그리고 나누기 연산은 0으로 나누면 예외가 발생하므로 별도로 if문을 추가해주었습니다.
여기까지 해서 number를 1~9 사이의 숫자 N과 사칙연산으로 표현할 때, N 사용횟수의 최솟값을 구하는 코드를 작성해보았습니다.
아래는 전체코드입니다.
import java.util.HashSet;
import java.util.Set;
import java.util.ArrayList;
import java.util.List;
class Solution {
private void unionSet(Set<Integer> union,Set<Integer> aSet, Set<Integer> bSet) {
for(int a : aSet) {
for(int b : bSet) {
union.add(a + b);
union.add(a - b);
union.add(a * b);
if(b != 0) {
union.add(a / b);
}
}
}
}
public int solution(int N, int number) {
List<Set<Integer>> setList = new ArrayList<>();
if(N == number) return 1;
for(int i=0; i<9; i++) {
setList.add(new HashSet<>());
}
setList.get(1).add(N);
for(int i=2; i<9; i++) {
for(int j=1; j < i; j++) {
unionSet(setList.get(i), setList.get(i-j), setList.get(j));
}
String n = Integer.toString(N);
setList.get(i).add(Integer.parseInt(n.repeat(i)));
for(int num : setList.get(i)) {
if( num == number) return i;
}
}
return -1;
}
}'알고리즘' 카테고리의 다른 글
| 프로그래머스 - 여행경로 : Java (0) | 2023.08.31 |
|---|---|
| 프로그래머스 - 섬 연결하기 : Java (0) | 2023.08.29 |
