백준 2075 N번째 큰 수 - [알고리즘] [kotlin]

문제 내용

문제 분석

1. n*n 크기의 표가 있다.

2. n은 최대 1500으로 표의 최대 크기는 2250000 (2백만 이상)이다.

3. 각 수는 -10억 ~ 10억 의 범위를 갖는다.

4. 각 수는 바로 위에 배치된 수보다 크다.

5. n번째 큰 수를 찾아 출력한다.

 

아이디어

1. N번째 큰 수를 찾아야 하기 때문에 정렬으로 접근한다.

2. 모든 열은 정렬이 되어있는 상태이다.

3. mergeSort는 각 수를 쪼개서 정렬하며 올라오는 방식으로, 현 상태는 mergeSort의 중간단계로 볼 수 있다.

4. 각 열을 sort되어있다고 보고 mergeSort를 중간단계부터 구현한다.

5. n번째 index를 출력한다.

 

1. pq를 사용한다.

2. 값이 작을수록 중요도가 높게 설정한다.

3. pq의 크기는 n으로 유지한다.

4. 만약 n개가 꽉 차면 이번에 들어온 수와 pq의 가장 작은 수를 비교해, 더 큰것을 가져간다.

즉, 모든 수를 고려하고 나면, 가장 큰 n개의 숫자가 pq에 남아있게 된다.

5. pq의 top을 출력한다.

 

풀이

/**
 * mergeSort의 중간 단계라고 생각하고 merge Sort를 구현한다.
 * */
// 1176ms
fun mergeSort() {

    val br = System.`in`.bufferedReader()

    val n = br.readLine().toInt()

    val arr = Array(n){ IntArray(n) }

    // 각 배열을 열별로 받는다.
    // 각 배열은 오름차순으로 정렬된 상태이다.
    for(i in 0 until n) {
        val tmpArr = br.readLine().split(' ').map { it.toInt() }
        for(j in 0 until n) {
            arr[j][i] = tmpArr[j]
        }
    }
    br.close()

    // queue의 크기가 1이 될떄까지 정렬을 유지하며 합친다.
    val q = LinkedList<IntArray>().apply {
        addAll(arr)
    }

    fun getMergedArr(a: IntArray, b: IntArray): IntArray {
        // 두 배열을 합치는 함수
        // 이때 정렬된 상태로 return한다.
        var indexA = 0
        var indexB = 0
        return IntArray(a.size + b.size) {
            if(indexA == a.size) b[indexB++]
            else if(indexB == b.size ) a[indexA++]
            else if(a[indexA] < b[indexB]) a[indexA++]
            else b[indexB++]
        }

    }

    while(q.size > 1) {
        val a = q.removeFirst()
        val b = q.removeFirst()

        q.addLast(getMergedArr(a,b))
    }

    print("${q.last[n*n-n]}")
}

/**
 * 큰 수들의 모임이라는 의미로 MinHeap을 만든다.
 * MinHeap의 크기는 n개로 크기를 제한한다.
 * 만약 더이상 넣을 수 없다면 가장 작은 것과 비교 후 큰것을 넣는다.
 * */
// 1372ms
fun pqSolve() {

    val br = System.`in`.bufferedReader()

    val n = br.readLine().toInt()

    // 작은 수가 top에 오게 함 (minHeap)
    val pq = PriorityQueue<Int> { a,b -> a-b }
    fun PriorityQueue<Int>.pushWithMax(num: Int) {
        if(pq.size < n) {
            this.add(num)
        }
        else if( pq.peek() < num){
            this.poll()
            this.add(num)
        }
    }

    repeat(n) {
        val arr = br.readLine().split(' ').map { it.toInt() }
        arr.forEach { pq.pushWithMax(it) }
    }
    br.close()

    print("${pq.peek()}")

}

bruteForce한 방식도 통과했다.

/**
 * 내장 sort 함수를 이용해 sort 후 n번째로 큰 원소룰 출력한다.
 * */
// 1492ms
fun sortBruteForce() {
    val br = System.`in`.bufferedReader()

    val n = br.readLine().toInt()
    val arr = IntArray(n*n)

    for(i in 0 until n) {
        val tmpArr = br.readLine().split(' ').map { it.toInt() }
        for(j in 0 until n) {
            arr[n*i + j] = tmpArr[j]
        }
    }

    arr.sortDescending()

    print("${arr[n-1]}")
}


/**
 * MaxHeap에 모든 원소를 넣고 N번 뽑아낸다. (sort와 논리적으로 같다.)
 * */
// 1484ms
fun pqBruteForce() {

    val br = System.`in`.bufferedReader()

    val n = br.readLine().toInt()

    // 작은 수가 top에 오게 함 (minHeap)
    val pq = PriorityQueue<Int> { a,b -> b-a }

    repeat(n) {
        val arr = br.readLine().split(' ').map { it.toInt() }
        arr.forEach { pq.add(it) }
    }
    br.close()

    repeat(n-1) {
        pq.poll()
    }

    print("${pq.peek()}")

}