[백준][Kotlin]1377번 버블 소트

해당문제는 문제설명에 있는 버블정렬을 사용시 시간초과가 발생하는 문제입니다.

따라서 버블정렬을 사용하지 않고 스왑이 몇번이 일어났는지 알아내야하는 문제입니다.

 

해당 자료를 받으면서 data class를 사용하여 해당 자료의 index와 value 값을 저장하여

value 값 기준으로 정렬 후 index 와 정렬 전 index 값의 최대 차이를 구한 후 +1 를 해주면 답을 구할 수 있는 문제였습니다.

 

하기는 작성한 코드와 채점현황입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Math.max
import java.util.*

data class info(val idx: Int, val value: Int)

fun main() {
//    val s = System.currentTimeMillis()
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    val N = st.nextToken().toInt() // 자료의 개수
    //var sb = StringBuilder()

    var arr = Array<info>(N+1){info(0,0)}

    repeat(N){
        arr[it+1] = info(it+1,br.readLine().toInt())
    }
    arr.sortWith(kotlin.Comparator { o1, o2 ->  o1.value.compareTo(o2.value)})

    var max = 0
    for(i in 1 .. arr.size-1){
        max = max(max,arr[i].idx-i)
    }
//    println(arr.toMutableList())
    bw.append((max+1).toString())
    bw.flush()
    bw.close()

//   val e = System.currentTimeMillis()
//   println((e-s)/1000.0)

}