[백준/Swift] 14003: 가장 긴 증가하는 부분 수열 5 | PS일지

문제

14003번: 가장 긴 증가하는 부분 수열 5

간단한 문제 요약

수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}. 길이 4.

 

문제 풀이

이 문제는 2568: 전깃줄 - 2 문제와 같습니다. 전깃줄 - 2 PS일지 포스트에 LIS 개념과 역추적 개념을 잊지 않기 위해 썼습니다. 전깃줄 2 에서도 결국 전봇대 B를 소팅하게 되면 A 전봇대의 각각의 데이터에 대해 LIS를 찾는 문제였는데 이 문제 또한 마찬가지 입니다.

 

이분 탐색을 활용한 LIS를 구현할 때 LIS를 통해 원소들이 추가되거나 교체되는 배열은 실제로 가장 긴 증가하는 부분 수열일수도 있고 아닐수도 있지만 LIS길이 반환은 확실합니다. 순차적으로 수열 A를 탐색할 때 dp배열에 각각 index에 대응하는 수열 A의 원소가 앞 원소들로부터 몇번째로 긴지 저장한 정보를 바탕으로 backtracking해서 답을 얻었습니다.

코드

//MARK: - Properties
_=readLine()
let lists = readLine()!.split{$0==" "}.map{Int(String($0))!}
var sequence = [lists.first!]
var dp = Array(repeating: 1, count: lists.count)

//MARK: - Helpers
func binarySearch(_ seq: inout [Int], target: Int) -> Int {
    var left = 0,right = seq.count-1,mid=0
    while left<right {
        mid = (left+right)/2
        if target>seq[mid] {
            left = mid + 1
        }else {
            right = mid
        }
    }
    seq[right] = target
    return right
}

func lis() {
    (1..<lists.count).map{
        if lists[$0] > sequence.last! {
            sequence.append(lists[$0])
            dp[$0] = sequence.count
        }else {
            let idx = binarySearch(&sequence, target: lists[$0]) + 1
            dp[$0] = idx
        }
    }
}
func backtracking() -> [Int] {
    var length = dp.max()!
    var res: [Int] = []
    for i in stride(from: lists.count-1, through: 0, by: -1) where dp[i] == length {
        res.append(lists[i])
        length -= 1
    }
    return res.reversed()
}

func solution() {
    lis()
    let sequence = backtracking()
    print(sequence.count)
    print(sequence
        .map{String($0)}
        .joined(separator: " "))
}

solution()