inequal

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. 부등호의 개수(k) + 1 만큼 0 ~ 9 사이의 정수를 전부 놓아보면서 부등호 관계를 비교해야 하므로,
2. k + 1개 만큼의 중첩 반복문이 필요하므로 Back-tracking 알고리즘으로 문제를 해결하는 것이 효율적
3. 가능한 답의 개수가 하나 이상 존재하므로 그 중에서 최대값 최소값을 찾기 위해서는 9부터(최대값) 숫자를 결정하고,
4. 0부터(최소값) 숫자를 결정함으로써 각각을 얻을 수 있음
5. 순열구하기 문제에서 처럼 중복을 확인하면서 부등호 관계가 만족하는지 결정해야 하고, 최초로 결정되는 숫자가 최대값 최소값 이므로 
6. Bool 변수를 하나 두어 최초로 완성되었을 때 true로 값을 바꿔주고, 재귀함수는 Bool 변수의 값이 true가 되면 종료되도록 구현함

5. 전체 코드

//MARK: - inequal

//MARK: - Framework
import Foundation

//MARK: - Variable
var flag: Bool = false

//MARK: - Function
func getMaxInequal(_ A: [String], _ current: Int, _ k: Int, _ lowerBound: Int, _ upperBound: Int, _ result: inout [Int], _ check: inout [Bool]) -> Void {
    if flag {
        return
    }
    
    if current >= k + 1 {
        var answer: String = ""
        for number in result {
            answer += "\(number)"
        }
        print(answer)
        flag = true
    } else {
        for i in stride(from: upperBound, through: lowerBound, by: -1) {
            if !check[i] {
                var isPossible: Bool = true
                
                if current == 0 {
                    isPossible = true
                } else {
                    switch A[current - 1] {
                    case "<":
                        isPossible = result[current - 1] > i ? false : true
                    case ">":
                        isPossible = result[current - 1] < i ? false : true
                    default:
                        break
                    }
                }
                
                if isPossible {
                    result[current] = i
                    check[i] = true
                    getMaxInequal(A, current + 1, k, lowerBound, upperBound, &result, &check)
                    check[i] = false
                }
            }
        }
    }
}

func getMinInequal(_ A: [String], _ current: Int, _ k: Int, _ lowerBound: Int, _ upperBound: Int, _ result: inout [Int], _ check: inout [Bool]) -> Void {
    if flag {
        return
    }
    
    if current >= k + 1 {
        var answer: String = ""
        for number in result {
            answer += "\(number)"
        }
        print(answer)
        flag = true
    } else {
        for i in lowerBound...upperBound {
            if !check[i] {
                var isPossible: Bool = true
                
                if current == 0 {
                    isPossible = true
                } else {
                    switch A[current - 1] {
                    case "<":
                        isPossible = result[current - 1] > i ? false : true
                    case ">":
                        isPossible = result[current - 1] < i ? false : true
                    default:
                        break
                    }
                }
                
                if isPossible {
                    result[current] = i
                    check[i] = true
                    getMinInequal(A, current + 1, k, lowerBound, upperBound, &result, &check)
                    check[i] = false
                }
            }
        }
    }
}

func solution() -> Void {
    //MARK: - Input
    guard let k: Int = Int(readLine() ?? "0") else { return }
    guard let A: [String] = readLine()?.components(separatedBy: " ") else { return }
    let lowerBound: Int = 0
    let upperBound: Int = 9
    
    var result: [Int] = Array(repeating: 0, count: k + 1)
    var check: [Bool] = Array(repeating: false, count: upperBound + 1)
    
    //MARK: - Process & Output
    getMaxInequal(A, 0, k, lowerBound, upperBound, &result, &check)
    
    check = Array(repeating: false, count: upperBound + 1)
    flag = false
    
    getMinInequal(A, 0, k, lowerBound, upperBound, &result, &check)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.