https://school.programmers.co.kr/learn/courses/30/lessons/42895
2023.08.28 기준 Level 3
알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!
아이디어
- Int형인 N과 number과 주어진다.
- N을 최소한으로 사용하여 사칙연산을 통해 number를 만들어야 한다.
- 이때 필요한 N의 최소 개수를 리턴해야 한다.
사칙연산으로 특정 숫자를 만들어야 하는 문제였습니다.
문제 분류 자체에 힌트가 있었습니다.
바로 동적 계획법 DP 입니다.
동적계획법은 BottomUp 방식으로 바닥부터 시작하여 구하고자 하는 단계까지 차례로 연산을 하여 정답을 구하는 방식입니다.
여기서 DP의 대상을 정하는 것이 중요한데 이 문제에서는 N의 개수를 기준으로 잡았습니다.
즉, N이 i개 사용했을 때 만들 수 있는 숫자들을 기록하면서 number를 만들 수 있는 순간에 i를 리턴하는 것입니다.
이 로직으로 처음 구현을 하다가 테스트 케이스에서 실패가 발생했었는데 그 원인은 i개 사용했을 때 만들 수 있는 숫자들을 구할 때 가능한 경우의 수들을 잘못 생각했기 때문이었습니다.
dp[i] = 사칙연산(dp[i-1], N) 이렇게 점화식을 세우고 i-1개로 만들 수 있는 숫자들에 한번의 사칙연산을 추가해서 i개로 만들 수 있는 숫자들을 구했으나 이것은 많은 경우를 빼먹는 문제가 있었습니다.
예를 들어 i가 6라면 6개의 N으로 만들 수 있는 숫자들을 전부 구해야 합니다.
이 상황에서 가능한 경우의 수는 다음과 같습니다.
- 1개의 N로 만들 수 있는 숫자 집합과 5개의 N으로 만들 수 있는 숫자 집합의 사칙연산
- 2개의 N로 만들 수 있는 숫자 집합과 4개의 N으로 만들 수 있는 숫자 집합의 사칙연산
- 3개의 N로 만들 수 있는 숫자 집합과 3개의 N으로 만들 수 있는 숫자 집합의 사칙연산
이렇게 3개의 경우를 모두 연산해주어야 하는데 1번의 경우만 연산해주었기 때문에 실패했었습니다.
4개의 N로 만들 수 있는 숫자 집합과 2개의 N으로 만들 수 있는 숫자 집합의 사칙연산 ➡️ 이건 2번의 경우와 겹치기 때문에 계산하지 않아도 됩니다.
다시 점화식을 세워보면
dp[i] = 사칙연산(dp[j], dp[i-j]), j는 [i, (i/2)]
입니다.
아! 그리고 문제를 잘 보면 단순 사칙연산 이외에도 1가지 경우를 더 고려해야 합니다.
N이 5이고 i가 3일 때 555가 가능하듯이 "NNN.." 형태로 N이 반복되는 경우도 고려해야 하기 때문에 이 수는 직접 집합에 추가시켰습니다.
이렇게 많은 경우의 수들을 전부 연산하면 시간 초과가 발생하지 않을까 싶었지만 마침 문제 조건에서 i가 8보다 커지면 -1을 리턴하라는 아주 적합한 조건이 있었습니다. (이렇게 모든 연산을 해보라는 의도로 낸 문제가 맞는 것 같습니다.)
i가 증가할 때 마다 가능한 숫자들이 매우 많아져서 실행 시간이 대폭 증가하지만 i가 8보다 커지면 더이상 연산을 안해도 되기 때문에 이러한 문제 풀이를 할 수 있었습다.
풀이
1. 사칙 연산 함수 구현
// 사칙연산 수행
fileprivate func doFourOperations(_ a: Int, _ b: Int) -> Set<Int> {
var res = Set<Int>()
res.insert(a + b)
res.insert(a - b)
res.insert(b - a)
res.insert(a * b)
if b != 0 {
res.insert(a / b)
}
if a != 0 {
res.insert(b / a)
}
return res
}
두 수를 받아 사칙 연산을 수행한 결과물을 집합으로 리턴하는 함수입니다.
여기서 빼기와 나누기는 연산 순서에 따라 결과가 달라지기 때문에 두 경우를 모두 연산하도록 했습니다.
2. solution 함수 구현
fileprivate func solution(_ N:Int, _ number:Int) -> Int {
var canMake = Array(repeating: Set<Int>(), count: 9) // Index: N의 개수, Value: Index개의 N으로 만들 수 있는 수의 집합
canMake[1] = [N]
if number == N {
return 1
}
for i in 2...8 {
var cur = Set<Int>() // i개의 N으로 만들 수 있는 수의 집합
cur.insert(Int(String(repeating: String(N), count: i))!) /// NNN
for j in 1...(i/2) {
let prev1 = canMake[j] // j개의 N으로 만들 수 있는 수의 집합
let prev2 = canMake[i-j] // i-j개의 N으로 만들 수 있는 수의 집합
for a in prev1 {
for b in prev2 {
cur.formUnion(doFourOperations(a, b))
}
}
}
if cur.contains(number) {
return i
}
canMake[i] = cur
}
return -1
}
canMake 배열에 index개의 N으로 만들 수 있는 수들의 집합을 기록합니다.
집합을 사용한 이유는 중복되는 수들을 제거하기 위해서입니다.
number가 N인 경우에는 1개의 N으로도 만족시킬 수 있기 때문에 곧바로 1을 리턴했습니다. (현재 기준 테스트케이스 9번을 통과하기 위해서는 꼭 이러한 처리가 필요했습니다.)
이제 i를 2부터 8까지 반복하며 i로 만들 수 있는 수들을 전부 구해서 canMake에 저장합니다.
NNN형태는 직접 문자열로 만들고 Int로 변환한 뒤 cur 집합에 넣었습니다.
cur에 number가 들어있다면 i개로 number를 만들 수 있다는 뜻이기 때문에 i를 리턴합니다.
마무리
개인적으로 DP 아이디어를 떠올리는 것이 어려운 것 같습니다.
이 문제는 분류 자체가 DP로 되어 있어서 비교적 쉽게 찾을 수 있었습니다.
그리고 문제 조건을 꼼꼼히 확인하여 최솟값이 8보다 크면 -1을 리턴하라는 조건을 놓치지 않았고 이를 통해 전부 연산해서 찾아야 한다는 아이디어에 확신을 가질 수 있었습니다.
'알고리즘' 카테고리의 다른 글
[프로그래머스] Swift - 등산코스 정하기 (0) | 2023.09.02 |
---|---|
[프로그래머스] Swift - 블록 이동하기 (0) | 2023.08.30 |
[프로그래머스] Swift - 스타 수열 (0) | 2023.08.25 |
[프로그래머스] Swift - 표현 가능한 이진트리 (0) | 2023.08.23 |
[프로그래머스] Swift - 미로 탈출 명령어 (0) | 2023.08.22 |
댓글