[백준 11650번] 좌표 정렬하기

 

단순하게 문제를 봤을 땐 중첩 for 문을 이용하면 쉽게 풀릴 수 있다고 생각할 수 있다.

 

하지만 100000 × 100000 은 이미 1초를 넘어가게 된다.

 

그러므로 중첩 for 문을 이용하는 것은 사용할 수 없다.

 

코틀린에서는 sortedWith 를 사용하면 O(nlogN) 의 시간 복잡도를 가지고 정렬을 할 수 있다.

 

chatGpt 설명 : 기본적으로 TimSort 알고리즘을 사용합니다. TimSort는 합병 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)을 결합한 알고리즘으로, 최선의 경우, 평균적인 경우, 최악의 경우 모두 O(n log n)의 시간복잡도를 가집니다.

 

 

코드)

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))

    val N = bf.readLine().toInt()

    val coordinateList: ArrayDeque<Pair<Int, Int>> = ArrayDeque()

    (0 until N).forEach {
        val st = StringTokenizer(bf.readLine())
        val x = st.nextToken().toInt()
        val y = st.nextToken().toInt()
        coordinateList.add(Pair(x,y))
    }
    val list = coordinateList.sortedWith(compareBy<Pair<Int,Int>>( {it.first} , {it.second}))

    list.forEach {
        println("${it.first} ${it.second}")
    }

}

 

 

여기서 compareBy( {it.first} , {it.second}) 를 하게되면 first 로 먼저 오름차순으로 정렬을 하다가 first 가 같으면 그 때 second 로 오름차순 정렬을 하게 해줍니다.