[백준] 2910번 빈도 정렬[Kotlin - 코틀린]

백준 2910번 문제입니다. (solved.ac) 기준 실버 3 문제입니다.

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

2910번: 빈도 정렬

문제

문제 접근

수열을 입력받아 빈도 정렬을 하여 출력하는 문제입니다.

수열내의 수를 빈도순으로 정렬하고 빈도수가 같다면 먼저 들어온 것이 앞으로 나오도록 정렬하면 되는 문제입니다.

처음에는 계수 정렬을 사용하려 했지만 숫자의 범위인 C의 범위가 1,000,000,000이하이기 때문에 계수정렬은 사용할 수가 없었습니다.. 그래서 Map 자료구조를 사용하였습니다. 그 중에서도 수정이 가능한 MutableMap<Int, Int>을 사용하여 MutableMap에 수열의 값(키)가 없다면 put을 통하여 추가해주고 값으로는 1을 지정해주었습니다. 만약 MutableMap에 수열의 값이 있다면 이미 키로 해당 수열이 존재한다는 것이기 때문에 해당 키의 값(value)를 1 더하여 주었습니다.

ex ) MuatableMap에 2 = 4와 같이 존재한다면 수열에서 2라는 값이 4번 나왔다는 뜻

수열을 전부 MutableMap에 입력받고나면 빈도 정렬을 진행해줍니다. MutableMap은 key로는 정렬이 가능하지만 value로는 정렬이 불가능 하기 때문에 toList를 사용하여 리스트로 변환시켜준 후 값을 기준으로 정렬 후 다시 toMap을 사용하여 Map으로 만들어 주었습니다.

Map을 List로 변환시키면 pair 로 변하게 됩니다. (Pari<Int,Int>) Pair의 첫 번째 값은 Map에서의 Key, 두 번째 값은 value입니다.

정렬을 할 때 second를 사용하여(value기준) 정렬하였습니다.

 

정답 코드

fun main() {

    val frequencySort = mutableMapOf<Int, Int>()
    
    // 계수 정렬을 사용하기에는 C의 범위가 1,000,000,000 이하라서 무리...
    val (N, C) = readln().split(" ").map { it.toInt() }

    val sequence = readln().split(" ").map { it.toInt() }

    sequence.forEach {
        if (frequencySort.containsKey(it)) {
            frequencySort[it] = frequencySort[it]!! + 1
        } else frequencySort.put(it, 1)
    }


    frequencySort.toList().sortedByDescending { it.second }.toMap()
        .forEach { map ->
            repeat(map.value) {
                print("${map.key} ")
            }
        }
}