[Swift 알고리즘] 백준 2529 (부등호)

 

https://www.acmicpc.net/problem/2529

2529번: 부등호

 

 

풀이 과정

부등호에 들어갈 수 있는 값들을 나열하고 만약 depth가 inputN과 똑같아진다면, 값을 비교한다.

브루스트포스이면서 시간복잡도는 10!이다. 

즉 DFS로 중간에 값을 쳐내면서 진행해도 1부터 10까지의 배열을 검사하는 단계를 각 자리수마다 진행하기에 높은 시간복잡도가 형성된다. 코드는 다음과 같다.

func sol2529() {
    let inputN = Int(readLine()!)!
    let inputString = readLine()!.split(separator: " ").map{String($0)}
    
    var targetString:[Int] = [] //">" 는 -1 "<" 는 1
    for i in inputString {
        if i == ">" {
            targetString.append(-1)
            continue
        }
        targetString.append(1)
    }
    var targetArr:[Bool] = Array(repeating: false, count: 10)
    var visitedArr:[Int] = []
    var minVal = 100000000000
    var maxVal = -100000000000
    
    func funcrecurc(_ currentInd: Int, _ postVal: Int) {
        if visitedArr.count == inputN + 1 {
            //print("count가 3일 때 \(visitedArr)")
            minVal = min(minVal, Int(visitedArr.map{String($0)}.joined())!)
            maxVal = max(maxVal, Int(visitedArr.map{String($0)}.joined())!)
            visitedArr.popLast()
            return
        }
        for i in 0..<10 {
            if targetArr[i] == false {
                //print("현재 인덱스는? \(currentInd), 현재 visited? = \(visitedArr)")
                if currentInd == 0 {}
                else if targetString[currentInd - 1] == 1 && postVal > i { continue }
                else if targetString[currentInd - 1] == -1 && postVal < i { continue }
                //print("여기 지남")
                visitedArr.append(i)
                targetArr[i] = true
                funcrecurc(currentInd + 1, i)
                targetArr[i] = false
                
            }
        }
        visitedArr.popLast()
    }
    funcrecurc(0, -1)
    var tempVal = 1
    print(maxVal)
    for _ in 0..<inputN { tempVal *= 10 }
    
    if minVal / tempVal == 0 {
        print("0", terminator: "")
    }
    print(minVal)
    
    
}
sol2529()

하지만 이 방법보다 깔끔하고 쉬운 방법이 있는데,

 

바로 appleBudy님의 코드이다. 이 코드를 보고 감탄을 받았는데, 이는 시간복잡도가 n^2 밖에 되지 않는다. 이 코드를 자세히보면 버블 sort를 활용한 것이다. 이렇게 깔끔하게 코드를 쓸 수 있다는 것에 적지않게 충격을 받았다. 역시 고수들은 너무 많구나... ㅠ_ㅠ 벽느껴진다.

import Foundation

func solve() {
    let K = Int(readLine()!)!
    var mV = [0,1,2,3,4,5,6,7,8,9]
    var MV = [9,8,7,6,5,4,3,2,1,0]
    let CV = readLine()!.split(separator: " ").map { String($0) }
    
    for i in 0..<K {
        for j in 0..<K-i {
            if CV[j] == ">" {
                if mV[j] < mV[j+1] { mV.swapAt(j, j+1) }
                if MV[j] < MV[j+1] { MV.swapAt(j, j+1) }
            } else {
                if mV[j] > mV[j+1] { mV.swapAt(j, j+1) }
                if MV[j] > MV[j+1] { MV.swapAt(j, j+1) }
            }
        }
    }
    
    var mxAns = "", miAns = ""
    for i in 0..<K+1 {
        mxAns += "\(MV[i])"
        miAns += "\(mV[i])"
    }
    
    print("\(mxAns)\n\(miAns)")
}

solve()