[백준] 1377번: 버블 소트

문제링크

• i번째 숫자가 i번째 이후 숫자보다 작은 경우의 수를 계산하면 될 것이라고 생각하여 Heap을 사용하여 해결해보려 했지만 시간 초과가 발생하였고, 세그먼트 트리를 사용하여 시간 초과를 해결해보고자 했지만 결국 틀렸다는 결과를 얻게 되어 가정이 잘못되었음을 깨달았다.
• 문제 해결 방법은 생각보다 간단했다. 버틀 소트는 오름차순의 경우 작은 수가 큰 수보다 뒤에 있을 때 Iteration을 진행할 때마다 한 칸씩 앞으로 전진한다는 사실만 이해하면 된다.
• 예를 들면, 10 1 5 2 3 수열이 주어졌을 때 첫 번째 Iteration을 진행하게 되면 1 5 2 3 10 수열을 얻게 된다. 즉, 1 5 2 3 은 10보다 작은 수이기 떄문에 한 칸씩 앞으로 전진했다.
• 이러한 사실을 기반으로 가장 많이 전진한 수가 최대 Iteration 횟수이기 때문에 해당 문제의 정답이라고 할 수 있다.

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    val numbers = mutableListOf<Pair<Int, Int>>()
    for (i in 0 until n) {
        val number = br.readLine().toInt()
        numbers.add(Pair(number, i))
    }

    val sorted = numbers.sortedBy { it.first }
    var maxMoved = 0
    sorted.forEachIndexed { index, number ->
        if (maxMoved < number.second - index) {
            maxMoved = number.second - index
        }
    }
    // 정렬된 후에도 checked == false 임을 확인하기 위한 for 문을 돌기 때문에 +1을 해줍니다.
    bw.write("${maxMoved + 1}")

    br.close()
    bw.close()
}

시간복잡도

O(N * logN)