[Algorithm] 백준 - 2529번 부등호 (Swift)

문제 소개

부등호가 주어지면 그 부등호에 맞는 숫자의 최소값, 최대값을 출력하는 문제이다.

 

문제 풀이

모든 숫자의 배열을 구하는 dfs 함수와 해당 배열과 부등호가 잘 맞는지 check 함수를 구했다. dfs 함수에서 depth > 0 && !check(current) 조건을 두어 조건에 맞지 않으면 바로 함수를 종료하도록 했다.

import Foundation

let k = Int(readLine()!)!
let input = readLine()!.split(separator: " ").map { String($0) }
let nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
var visited = Array(repeating: false, count: 10)
var answers = [[Int]]()

func dfs(_ current: [Int], _ depth: Int) {
    if depth > 0 && !check(current) {
        return
    }
    
    if depth == k+1 && check(current) {
        answers.append(current)
        return
    }
    
    for i in 0..<10 {
        if !visited[i] {
            visited[i] = true
            dfs(current + [nums[i]], depth+1)
            visited[i] = false
        }
    }
}

func check(_ array: [Int]) -> Bool {
    for i in 0..<array.count-1 {
        if input[i] == "<" {
            if array[i] > array[i+1] {
                return false
            }
        } else {
            if array[i] < array[i+1] {
                return false
            }
        }
    }
    
    return true
}

dfs([], 0)
let first = answers[0].map { String($0) }.joined()
let last = answers[answers.count-1].map { String($0) }.joined()

print(last)
print(first)