난이도 : Level 3
- 두 정수 N과 number가 주어진다
- number : 표현하고자 하는 수
- N : 표현하는데 사용되는 수
- N을 사칙연산만 사용해서 number를 표현해야 한다
- 표현할 수 있는 방법 중 N 사용횟수의 최솟값을 리턴하라
- 최솟값이 8보다 크면 -1을 리턴하라
- N : 1이상 9이하
- number : 1이상 32000이하
example) N : 5, number : 12
- 12 = 5 + 5 + (5 / 5) + (5 / 5)
- 12 = 55 / 5 + 5 / 5
- 12 = (55 + 5) / 5
=> 4
해설
- N을 1부터 8까지 사용해서 만들수 있는 수 생성
- 만들수 있는 수들 중, number가 포함되는지 체크
- 포함되어 있다면, 만드는데 사용된 횟수를 리턴한다
- 포함되지 않다면, N을 하나 올려 숫자 생성을 반복한다
1. 만들수 있는 수 생성
N을 1~8개를 사용하여 사칙연산으로 만들수 있는 수를 생성해야 합니다.
하나씩 생각해 보면,
N = 1 - {5} (5를 연속해서 한개 사용한 숫자)
N = 2 - {55, 5+5, 5-5, 5*5, 5/5} (5를 두개 연속해서 사용한 숫자, 5를 두개 사용하여 사칙연산한 값들)
여기까지는 쉽습니다. 3부터 복잡해집니다
N = 3 - {555, 55+5, 55-5, 55*5, 5/55, 5+55+, 5-55, 5*55, 5/55, 5+(5+5), 5+(5-5), 5+(5*5), 5+(5/5)...}
(5를 연속해서 세개 사용한 숫자, 5를 세개 사용하여 사칙연산한 값들)
5를 세개 사용하여 사칙연산한 숫자들 = (1, 2), (2, 1) 개의 N을 사칙연산한 숫자들의 유일한 값 이라 표현할 수 있습니다.
(1, 2)이 아닌 (1, 2), (2, 1)인 이유는 빼거나 나눌때 순서에 따라 값이 달라지므로 순서를 뒤바꾸어 나오는 결과값도 확인해보아야 합니다.
2. 동적 프로그래밍
Set 자료구조 활용
위에서 살펴본 수 생성을 보면 규칙이 존재합니다.
즉, 점화식 dp[i] = set(permutation(dp[1], [i-1]) ,permutation(dp[2], [i-2]), ... ,permutation(dp[i-1], [1]))
를 얻을 수 있습니다.
메모이제이션 기법을 적용하여 풀면 수월하게 풀 수 있습니다.
i개로 만들 수 있는 수들을 list의 i index에 Set 자료구조 안에 저장해둡니다 (중복제거)
N을 3개이상 사용해서 사칙연산한 숫자들의 순열해서 만드는데 사용합니다.
3. 코드
import java.util.*;
class Solution {
public int solution(int N, int number) {
if (number == N) {
return 1;
}
List<Set<Integer>> list = new ArrayList<>(N+1);
for (int a = 0; a < 9; a++) {
list.add(new HashSet<>());
}
list.get(1).add(N);
Set<Integer> min, max, set;
for (int i = 2; i < 9; i++) {
set = list.get(i);
set.add(Integer.parseInt(String.valueOf(N).repeat(i)));
for (int j = 1; j < i; j++) {
min = list.get(j);
max = list.get(i-j);
for (Integer i1 : min) {
for (Integer i2 : max) {
set.add(i1+i2);
set.add(i1-i2);
set.add(i1*i2);
if (i2 != 0) {
set.add(i1/i2);
}
}
}
}
if (set.contains(number)) {
return i;
}
}
return -1;
}
}
참고
'Algorithm > (Java) PS' 카테고리의 다른 글
[Programmers] 사칙연산 (0) | 2023.09.23 |
---|---|
[Programmers] 정수 삼각형 (0) | 2023.09.22 |
[Programmers][Kakao] 캠핑 (0) | 2023.09.21 |
[Leetcode Top Interview 150] 128. Longest Consecutive Sequence (2) | 2023.09.17 |
[Leetcode Top Interview 150] 202. Happy Number (0) | 2023.09.16 |