백준 2075번: N번째 큰 수 (Kotlin)

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

풀이

간단한 규칙이 있는 이차원 배열 수들 중 n번째로 큰 수를 찾는 문제였다.

 

공간 복잡도: 1500 *1500 * 4 byte = 9MB

시간 복잡도: 2,250,000 * log(2,250,000) = 2,250,000 * 21. ~ = 약 47,250,000

처음엔 복잡도가 충분해보였고 혹시 공간 복잡도에 문제가 있을까 싶었지만, 우선 일차원 배열을 정렬해서 답을 구해봤다. 그리고 예상외로 시간초과 판정을 받았다.

왜 시간초과가 발생했는지 찾아봤는데, 자바의 Array와 Collections의 정렬 방식이 다르기 때문이었다.
정렬의 실제 시간 복잡도는 C * 시간복잡도 + a로 알고리즘에 따라 C값이 달라지는데, Array는 퀵정렬을, Collections은 Tim 정렬이라는 걸 사용한다고 한다. 그 이유는, Array는 데이터들이 메모리에 연속적으로 존재하는 반면, list는 산발적인 연결리스트 방식으로도 존재해서 참조 지역성에 차이가 있기 때문이다. 그래서 리스트를 사용했을 때 시간 초과가 났고, IntArray로 풀어봤더니 정말로 됐다ㅋㅋ 

(자세한 내용은 https://sabarada.tistory.com/138 여기를 참고했습니다ㅋ.ㅋ)

 

 

다시 문제로 돌아와서, 고민하다가 풀이를 찾아보니 heap 또는 우선순위 큐를 사용하는 문제였다. 문제에서 주어진 배열의 크기 조건에 관계 없이 heap의 특징을 사용해서 쉽게 푸는 방법과 문제 조건을 함께 사용하는 방법이 있었고, 후자의 방법이 조금 더 빨랐다. 

참고) https://jihogrammer.tistory.com/25

 

 

방법1)

아이디어는 간단하다. 연산을 끝마쳤을 때 heap에 가장 큰 수 n개가 들어있게 만든다면, 그 중 최소 값이 n번째로 큰 수가 된다. 그러기 위해서, 최소heap에 수를 하나씩 넣는다. 그리고 크기를 n으로 유지하기 위해 최소 값을 삭제하고 새로운 숫자를 삽입하면, 연산할 때마다 최소 값이 하나씩 사라지므로 연산이 끝났을 때의 n개의 숫자들이 가장 큰 수의 집합이 된다. 

 

방법2)

두 번째 방법은 방법1에서 heap의 연산(logn) 횟수를 절약하는 것이다. 방법1에서는 연산을 할 때마다 heap에서 값을 빼고 넣는데, 사실 heap의 목적은 최소 값을 버림으로써 지금까지의 숫자들 중 최대 값 n개를 유지하는 것이다. 따라서, heap의 최소 값보다 작은 수는 연산할 필요가 없으므로 생략한다.

 

방법3)

세 번째는 heap과 더불어 문제의 조건도 함께 사용하는 방법이다. 다시 한번 말하지만, 핵심은 연산할 때마다가 아닌, 연산이 모두 끝났을 때 가장 큰 숫자 n개를 갖고 있는 것이다!

 

아이디어) 최대 heap을 사용한다. 처음에 heap이 전체의 최대 값을 갖고 있고, n-1번의 연산 동안 최대 값을 그 다음의 최대 값으로 교체할 수 있다면, 그때 최대heap의 값이 답이 된다.

 

이해하면 간단할 수도 있는데, 다이나믹 프로그래밍적인 느낌도 들고 처음부터 떠올리기엔 쉽지 않은 것 같다ㅋㅋ

 

구현 방법)

1. 이차원 배열에 숫자를 입력 받는다.

2. 마지막 행의 수들을 최대heap에 넣는다.

3. 그러면 heap은 처음에 가장 큰 수를 포함해서 각 열의 최대 값을 갖게 된다.

4. heap의 최대 값을 삭제한다.

5. 삭제한 값을 numbers[row][col]라고 할 때, heap에 numbers[row-1][col]을 삽입한다. 그럼 항상 모든 열의 최대 값을 heap이 갖게 되는데, 전체 수의 최대 값은 항상 모든 열의 최대 값 중 하나이다.

6. 따라서 이 연산을 n-1번 반복했을 때, 힙의 최대 값이 n번째로 큰 수가 된다.

 

구현을 위해선 이차원 배열에 값을 저장해놓고, 힙에 배열의 좌표를 함께 저장해야 한다. 

 

코드1

import java.util.*

fun main() {
    val n = readLine()!!.toInt()
    val pq = PriorityQueue<Int>() // 최소힙

    // 힙의 사이즈를 n으로 유지한다
    pq.addAll(readLine()!!.trim().split(" ").map{it.toInt()}) // 힙에 첫번째 줄 삽입
    repeat(n-1){
        val list = readLine()!!.trim().split(" ").map{ it.toInt() }
        list.forEach { number ->
            pq.offer(number)
            pq.poll()
        }
    }

    // 가장 큰 n개의 수만 남아있다
    println(pq.poll())
}

 

코드2

import java.util.*

fun main() {
    val n = readLine()!!.toInt()
    val pq = PriorityQueue<Int>(n) // 최소힙

    pq.addAll(readLine()!!.trim().split(" ").map{it.toInt()}) // 첫번째 줄 삽입
    
    repeat(n-1){
        val list = readLine()!!.trim().split(" ").map{ it.toInt() }
        list.forEach { number ->
            // 최대 값 n개를 유지한다 -> 힙의 최소 값보다 작은 수는 넣을 필요가 없다
            // 힙 연산 횟수를 줄이기 위해 힙의 최소 값보다 작은 수는 생략
            if (pq.peek() < number){	  
                pq.poll()
                pq.offer(number)
            }
        }
    }

    // 가장 큰 n개의 수만 남아있다
    println(pq.poll())
}

 

코드3

// 시간을 더 단축해보고 싶어서 StringTokenizer 사용했습니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class Number(val row: Int, val column: Int, val number: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val numbers = Array(n){ mutableListOf<Number>() }

    // 이차원 배열에 좌표와 함께 저장
    repeat(n){ i ->
        val st = StringTokenizer(readLine())
        for(j in 0 until n){
            val number = st.nextToken().toInt()
            numbers[i].add(Number(i, j, number))
        }
    }

    // 최대heap
    val pq = PriorityQueue<Number>(compareByDescending{it.number}).apply{
        addAll(numbers[n-1])    // 가장 큰 수가 들어있는 마지막 라인 추가
    }
    
    // 가장 큰 수를 차례대로 n-1번 꺼낸다
    repeat(n-1){
        val maxNumber = pq.poll()
        pq.add(numbers[maxNumber.row-1][maxNumber.column]) // 그 다음으로 가장 큰 수 n개 유지
    }

    println(pq.peek().number)
}