[백준] 10814번 나이순 정렬

10814번 나이순 정렬

접근 방법

Stable Sorting을 이용할 경우에 나이순으로 정렬하면 된다.

풀이 방법

주어진 Sort함수가 아닌 Sort를 구현해서 풀어보았다. 하지만 시간 초과로 인해 다른 방법을 찾아야했다.
시간 초과의 원인은 시간복잡도가 O(n^2)인 로직때문이었다.

그래서 전체 n개수를 줄이고자 map의 key값으로 나이를 저장해놓고 list에 이름을 넣는 방식을 선택했다.
이후에 값을 가져올 때 key값을 sort하는 함수를 만들었고 문제를 풀 수 있었다.

이때 Key가 정렬되어있는 맵을 이용하면 sort부분을 줄일 수 있겠다고 생각이 들었다.
또한 이것도 사이즈가 201인 Array를 만들어서 해당 나이에 이름을 넣어준 후 나중에 array를 돌며 출력해주어도 된다.

Code

import java.io.BufferedReader
import java.io.InputStreamReader

class IO10814 {
    private val br = BufferedReader(InputStreamReader(System.`in`))

    fun getInt(): Int {
        return br.readLine().toInt()
    }

    fun getPersonInfo(id: Int): Person {
        val (age, name) = br.readLine().split(" ")
        return Person(id, age.toInt(), name)
    }
}

data class Person(val id: Int, val age: Int, val name: String)

fun main() {
    val map = Map()
    sortKey(map.hashMap.keys).forEach { key ->
        map.hashMap[key]!!.forEach { person ->
            println("${person.age} ${person.name}")
        }
    }
}

fun sortKey(key: Set<Int>): MutableList<Int> {
    val keyList = key.toMutableList()
    val lIdx = keyList.lastIndex
    (0 until lIdx).forEach { count ->
        for (i in 1..lIdx-count) {
            val prev = keyList[i-1]
            val now = keyList[i]
            if (prev > now) {
                keyList[i-1] = now
                keyList[i] = prev
            }
        }
    }
    return keyList
}

class Map {
    private val _hashMap: HashMap<Int, MutableList<Person>> = hashMapOf<Int, MutableList<Person>>().apply {
        (1..200).forEach {
            put(it, mutableListOf<Person>())
        }
    }
    val hashMap get() = _hashMap
    private val io = IO10814()

    init {
        fillPerson()
    }

    private fun fillPerson() {
        val peopleCount = io.getInt()
        (1..peopleCount).forEach {
            val person = io.getPersonInfo(it)
            _hashMap[person.age]!!.add(person)
        }
    }
}