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

---

 

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

 

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

 먼저 (A-B) 쌍으로 이루어진 전깃줄을 A를 기준으로 오름차순 정렬해준다. 전깃줄이 교차하지 않으려면, A 오름차순으로 정렬했을 때 B도 오름차순이어야 한다. A는 증가하는데, B는 감소하면 전깃줄이 교차한다.

 

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

  전깃줄을 최소 개수로 제거해서 교차가 없게 만들려면, 남는 전깃줄의 개수를 최대로 만들어야 한다. 즉, 가장 긴 증가하는 부분 수열을 구하면 된다. N이 작기 때문에 O(N^2) 알고리즘으로도 충분하다. (아래 코드에서는 O(NlogN) 알고리즘을 사용했다.)

 

3. N - LIS가 없애야하는 전깃줄의 최소 개수이다.

 가장 긴 증가하는 부분 수열의 길이가 남아있는 전깃줄의 최대 개수이므로, N - LIS의 값이 제거해야하는 전깃줄 수의 최솟값이 된다.

---

import Foundation

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

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

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() -> Int {
    for i in 0..<N {
        let x = arr[i].B
        
        if lis.last! < x {
            lis.append(x)
        } else {
            let lb = lowerBound(x: x)
            lis[lb] = x
        }
    }
    
    return lis.count - 1
}

func solution() {
    N = Int(readLine()!)!
    
    arr = Array(repeating: (0,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 = N - LIS()
    print(result)
}

solution()