백준 2568 전깃줄 -2 Kotlin (LIS,이분탐색)

문제 출처 : https://www.acmicpc.net/problem/2568

2568번: 전깃줄 - 2

문제

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, <그림 1>과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 

<그림 1>

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 최소 개수의 전깃줄을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. 

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다. 둘째 줄부터 한 줄에 하나씩 없애야 하는 전깃줄의 A전봇대에 연결되는 위치의 번호를 오름차순으로 출력한다. 만약 답이 두 가지 이상이라면 그 중 하나를 출력한다.

알고리즘 분류

• 가장 긴 증가하는 부분 수열: o(n log n)

풀이

2021.04.19 - [알고리즘 문제 풀이/백준] - 백준 11053 가장 긴 증가하는 부분 수열 c++,Kotlin (dp)

2021.09.10 - [알고리즘 문제 풀이/백준] - 백준 12015 가장 긴 증가하는 부분 수열 2 Kotlin (dp)

2021.04.22 - [알고리즘 문제 풀이/백준] - 백준 2565 전깃줄 c++

이 문제를 풀기 전에 위의 가장 긴 증가하는 부분 수열 시리즈를 먼저 풀어보는 것을 추천한다.

아마 이 문제를 푸는 사람은 전깃줄 문제는 당연히 풀었을 거라 생각하고 글을 작성한다.

LIS(가장 긴 증가하는 부분 수열)에 관한 풀이는 위의 게시글에 작성했으니 따로 설명하진 않겠다.

 

기존의 전깃줄 문제에서 확장된 문제인데, 다른 점은, 기존 LIS를 만드는 과정은 두 개의 반복문으로 O(N^2)의 시간 복잡도였다. 하지만 이 문제는 입력이 10만이기 때문에, O(N^2)로 풀면 시간 초과가 뜬다.

그래서 LIS를 만드는 시간을 줄이고자 LIS 알고리즘에 이분 탐색을 곁들인다.

이에 대한 풀이는 가장 긴 증가하는 부분 수열 2 게시글을 확인하기 바란다.

덧붙이자면, 이분 탐색을 이용한 O(NlogN) LIS 풀이는 가장 긴 증가하는 부분 수열의 길이만 저장하는 것이 아니라,

LIS 배열을 실제로 만들고, 그 배열의 사이즈가 가장 긴 증가하는 부분 수열의 길이가 된다.

하지만, 이 LIS 배열은, 가장 긴 증가하는 부분 수열의 길이는 보장하지만, 가장 긴 증가하는 부분 수열에 사용된 값들을 보장하진 않는다.

 

예를 들어,

10 20 10 50 15에서 위에서 사용한 풀이로 LIS 배열을 만든다면

LIS = {15, 20, 50} 이 되므로, 실제 LIS인 10 20 50이 아니다.

 

그래서 우린 인덱스 배열이 필요하다.

input = {10, 20, 10, 50, 15} 이 주어졌을 때,

index 배열이란, 10이 LIS의 어디서 사용되었는지, 20이 LIS의 어디서 사용되었는지, 10이 LIS의 어디서 사용되었는지, 50이 LIS의 어디서 사용되었는지, 15가 LIS의 어디서 사용되었는지 인덱스를 저장한다.

이후, LIS의 인덱스에 맞춰서 index 배열을 뒤에서부터 추적하면 실제 LIS에 사용된 숫자들이 나온다.

 

직접 LIS 배열과 idx배열을 구해보자.

 

input[0] 탐색

LIS = {10}

idxArr = {0}

 

input[1] 탐색

LIS = {10, 20}

idxArr = {0, 1}

 

input[2] 탐색

LIS = {10, 20}

idxArr = {0, 1, 2}

 

input[3] 탐색

LIS = {10, 20, 50}

idxArr = {0, 1, 0, 2}

 

input[4] 탐색

LIS = {15, 20, 50}

idxArr = {0, 1, 0, 2, 0}

 

LIS의 마지막 인덱스는 2이고 LIS의 길이는 3이다.

이제 idxArr를 추적하여 실제 사용된 값을 찾아보자.

//LIS의 인덱스 = lisIdx

 

lisIdx(2) != idxArr[4](0)

lisIdx(2) == idxArr[3](2) -> input[3]이 사용됨 (50)

lisIdx(1) != idxArr[2](0) 

lisIdx(1) == idxArr[1](1) -> input[1]이 사용됨 (20)

lisIdx(0) == idxArr[0](0) -> input[0]이 사용됨 (10)

 

이제 LIS의 길이와 사용된 값을 구했으니,

전체 전깃줄의 개수에서 LIS의 길이를 뺀 값을 출력하고,

LIS에 사용된 값을 제외한 나머지 값들을 A기둥의 전깃줄을 오름차순으로 출력하면 끝! 

코드

fun biInsert(num : Int, dp : IntArray, start : Int, end : Int, lastIdx : Int) : Int{
    val mid = (start+end)/2
    if(start>=end){
        dp[mid] = num
        return mid
    }
    if(dp[mid]>num){
        return biInsert(num,dp,start,mid,lastIdx)
    }
    else{
        return biInsert(num,dp,mid+1,end,lastIdx)
    }
}

fun main() = with(System.out.bufferedWriter()) {
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val edge = Array<Pair<Int,Int>>(n){Pair(0,0)}
    val lis =  IntArray(n)
    val idxArr = IntArray(n)
    val used = BooleanArray(500001)
    for(i in 0 until n){
        val (from,to) = br.readLine().split(' ').map{it.toInt()}
        edge[i]= Pair(from,to)
    }
    edge.sortWith(Comparator{ a,b ->
        when{
            a.first < b.first -> -1
            else -> 1
        }
    })
    lis[0]=edge[0].second
    idxArr[0]=0
    var lisIdx=1
    for(i in 1 until edge.size){
        //이전 전깃줄이 현재 전깃줄보다 위에 연결된 경우
        if(lis[lisIdx-1]<edge[i].second){
            lis[lisIdx++]=edge[i].second
            idxArr[i]=lisIdx-1
        }
        else{
            val idx = biInsert(edge[i].second, lis,0, lisIdx,lisIdx-1)
            idxArr[i]=idx
        }
    }
    var len = lisIdx-1
    for(i in idxArr.size-1 downTo 0 ){
        if(len==idxArr[i]){
            used[edge[i].first]=true
            len--
        }
    }
    write("${n-lisIdx}\n")

    for(pair in edge){
        if(used[pair.first])continue
        write("${pair.first}\n")
    }
    close()
}