https://www.acmicpc.net/problem/2529
[문제]
두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.
A ⇒ < < < > < < > < >
부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다.
3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0
이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다.
5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4
여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1) 자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.
여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)와 같이 첫자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.
[입출력 예]
[풀이]
가능한 경우의 수에서 DFS 탐색으로 푸는 문제입니다.
핵심 함수는 아래와 같습니다.
fun dfs(prev: Int, count: Int, str: String) {
if (count == N) {
list.add(str)
} else {
for (next in 0 until 10) {
if (!check[next]) {
if (input[count] == "<") {
if (prev > next) continue
} else {
if (prev < next) continue
}
check[next] = true
dfs(next, count + 1, str + next)
}
}
}
check[prev] = false
}
count가 N과 같아지면, 즉 N + 1개의 숫자를 모두 선택했다면, 현재의 숫자 조합을 list에 추가합니다.
첫 번째 예제라면 length 3짜리 숫자 조합을 추가하는 것이죠.
아직 다를 경우에는 방문하지 않은 숫자를 찾고 현재 비교하는 부등호에 따라 이전과 현재 값의 크고 작은 관계를 판단해줍니다.
그리고 방문 상태를 갱신해 주고, dfs를 다음 값, length + 1, 축적 str를 반영하여 재귀호출해 줍니다.
아래는 코틀린 전체 코드입니다.
fun main() = with(System.in.bufferedReader()) {
var N = readLine().toInt()
var input = readLine().split(" ")
val check = BooleanArray(10)
val list = mutableListOf<String>()
fun dfs(prev: Int, count: Int, str: String) {
if (count == N) {
list.add(str)
} else {
for (next in 0 until 10) {
if (!check[next]) {
if (input[count] == "<") {
if (prev > next) continue
} else {
if (prev < next) continue
}
check[next] = true
dfs(next, count + 1, str + next)
}
}
}
check[prev] = false
}
for (now in 0 until 10) {
check[now] = true
dfs(now, 0, now.toString())
}
list.sort()
println(list.last())
println(list.first())
}오름차순 정렬된 리스트에서 최대 최소 값을 반환합니다.
