백준 2568번 전깃줄 - 2 - 스위프트(Swift) 풀이

---

 

1. 전깃줄들을 A를 기준으로 오름차순 정렬한다.
2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열을 구한다.
3. (N - LIS길이)가 없애야 하는 전깃줄의 최소 개수이며, LIS에 속하지 않는 전깃줄이 제거해야하는 전깃줄이다.

 

1. 전깃줄들을 A를 기준으로 오름차순 정렬한다.

 2565번 문제에서 제거해야 하는 전깃줄 목록까지 추가로 구하는 문제이다. 기본 원리는 아래와 같다.

백준 2565번 전깃줄 - 스위프트(Swift) 풀이

 

2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열을 구한다.

 N=10^5이므로 O(NlogN) 알고리즘을 사용해야 한다. 그리고 LIS 길이뿐만 아니라 LIS 자체도 구해야 한다.

 

3. (N - LIS길이)가 없애야 하는 전깃줄의 최소 개수이며, LIS에 속하지 않는 전깃줄이 제거해야 하는 전깃줄이다.

가장 긴 증가하는 부분 수열의 길이가 남아있는 전깃줄의 최대 개수이므로, N - LIS의 값이 제거해야하는 전깃줄 수의 최솟값이고, LIS에 속하는 전깃줄이 남아있는 전깃줄이므로, LIS에 속하지 않는 전깃줄들이 모두 제거 대상이다. 

 

---

import Foundation

typealias Pair = (A: Int, B: Int)

var N = 0
var arr = [Pair]()
var lis = [0]
var pos = [Int]()

func lowerBound(x: Int) -> Int {
    var lo = 0, hi = lis.count-1
    
    while lo < hi {
        let mid = (lo + hi) / 2
        
        if lis[mid] < x { lo = mid + 1 }
        else { hi = mid }
    }
    
    return lo
}

func LIS() {
    for i in 0..<N {
        let x = arr[i].B
        
        if lis.last! < x {
            pos[i] = lis.count
            lis.append(x)
        } else {
            let lb = lowerBound(x: x)
            pos[i] = lb
            lis[lb] = x
        }
    }
}

func notBelongToLIS() -> [Int] {
    LIS()
    
    var result = [Int]()
    var index = N - 1
    
    for k in (1..<lis.count).reversed() {
        while index >= 0 && pos[index] != k {
            result.append(arr[index].A)
            index -= 1
        }
        
        index -= 1
    }
    
    while index >= 0 {
        result.append(arr[index].A)
        index -= 1
    }
    
    return result.sorted()
}

func solution() {
    N = Int(readLine()!)!
    
    arr = Array(repeating: (0,0), count: N)
    pos = Array(repeating: 0, count: N)
    
    for i in 0..<N {
        let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        let A = input[0]
        let B = input[1]
        
        arr[i] = (A, B)
    }
    
    arr.sort(by: { $0.0 < $1.0 })   // A를 기준으로 오름차순 정렬
    
    let result = notBelongToLIS()   // 전깃줄이 교차하지 않으려면 B가 증가 수열이어야 함
    
    var resultString = "\(result.count)\n"
    result.forEach{ resultString.write("\($0)\n") }
    print(resultString)
}

solution()