728x90
https://www.acmicpc.net/problem/2529
2529번: 부등호
여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력
www.acmicpc.net
처음에 틀렸던 이유(시간초과)는, 모든 경우의 수를 탐색했기 때문(DFS)
그러나, 모든 경우의 수를 볼 필요가 없다! 조건에 맞지 않는 애는 가지치기 (BackTracking)
이 문제에서는 주어진 부등호에 맞게 숫자를 나열해야 하기 때문에
주어진 부등호를 사이에 넣었을 경우 해당 숫자들이 맞지 않다면 이제 그 경우는 바로 끝이다. 끝까지 갈 필요가 없다!
그러므로, 우선 BT의 종료 조건을 2가지로 나누어준다.
- 선택한 숫자들로 부등호 비교를 해봤을 경우, 올바르지 않다면 return → 다른 경우의 수로 넘기기(가지치기)
- 모든 숫자를 선택했을 경우(1번으로 인해 이 경우는 올바른 값이라는 것을 보장) → min, max 갱신하고 return → 다른 경우의 수 보기(가지치기)
+ 중복 불필요하므로 visit으로 0과 9 사이 수를 여러번 선택하지 않도록 한다.
import Foundation
/*
부등호 고정
선택되는 숫자가 다르다
k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다.
각 부등호의 앞뒤에 들어가는 숫자는 0~9 중 하나. 선택된 숫자는 모두 다르게
*/
//input
let n = Int(readLine()!)!
let inequality = readLine()!.split(separator: " ")
var visit = [Bool](repeating: false, count: 11)
var maxv = Int.min
var minv = Int.max
//DFS를 이용한 백트래킹 -> 매 노드마다 조건을 확인해서 바로 가지치기! -> 불필요한 연산 & 노드 체크 안할 수 있음
func BT(_ k: Int, _ num: [Int]) {
if k >= 2 { //2개 이상이 되어야 비교할 수 있으므로
if inequality[k - 2] == "<" && num[k-2] > num[k-1] { return }
else if inequality[k - 2] == ">" && num[k-2] < num[k-1] { return }
}
if k == n + 1 {
let number = num.reduce(into: 0) { $0 = $0 * 10 + $1 }
maxv = max(maxv, number)
minv = min(minv, number)
return
}
for i in 0...9 {
if !visit[i] {
visit[i] = true
BT(k+1, num + [i])
visit[i] = false
}
}
}
func insertZero(_ str: Int) -> String {
var str = String(str)
while str.count < n + 1 {
str.insert("0", at: str.startIndex)
}
return str
}
BT(0, [])
print("\(insertZero(maxv))\n\(insertZero(minv))")
728x90
