14003 swift - 가장 긴 증가하는 부분 수열 5

LIS의 플래티넘 버전. 수열 문제들을 풀다보면 어렵지 않게 풀 수 있다.

• 11053번. 가장 긴 증가하는 부분 수열
• 11054번. 가장 긴 바이토닉 부분 수열
• 11055번. 가장 큰 증가하는 부분 수열
• 11722번. 가장 긴 감소하는 부분 수열
• 12015번. 가장 긴 증가하는 부분 수열 2
• 12738번. 가장 긴 증가하는 부분 수열 3
• 14002번. 가장 긴 증가하는 부분 수열 4

dp로 풀면 O^2이므로 이진탐색을 이용하여 현재 수열들을 교체해가며 뽑아주고, 마지막 indices의 요소를 사용하여 parent를 역추적하여 뽑아내주면 된다.

import Foundation

var arr: [Int] = []
var sequence: [Int] = []
var indices: [Int] = []
var parent: [Int] = []
var N: Int = 0

func binarySearch(_ num: Int) -> Int {
    var low = 0, high = sequence.count - 1
    var mid = 0
    while low <= high {
        mid = (low + high) / 2
        let here_num = sequence[mid]
        if here_num >= num {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return low
}

func findLIS() {
    sequence.append(arr[0])
    indices.append(0)
    parent.append(-1)

    for i in 1..<N {
        if sequence.last! < arr[i] {
            parent.append(indices.last!)
            sequence.append(arr[i])
            indices.append(i)
        } else {
            let pos = binarySearch(arr[i])
            sequence[pos] = arr[i]
            indices[pos] = i
            parent.append(pos > 0 ? indices[pos - 1] : -1)
        }
    }
}

func reconstructLIS() -> [Int] {
    var lis: [Int] = []
    var currentIndex = indices.last!
    while currentIndex != -1 {
        lis.append(arr[currentIndex])
        currentIndex = parent[currentIndex]
    }
    return lis.reversed()
}

N = Int(readLine()!)!
arr = readLine()!.split(separator: " ").map { Int(String($0))! }

findLIS()

let lis = reconstructLIS()
print(lis.count)
print(lis.map{ String($0) }.joined(separator: " "))