[백준 10989] 수 정렬하기 3 | kotlin

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

문제 풀이

처음엔 속도 제한, 메모리 제한을 신경쓰지 않고 풀다가 계속 메모리 초과, 시간 초과가 나와서 어지러웠다..

그러던 와중 Counting sort(계수 정렬)에 대한 언급이 문제 하단에 있길래 해당 알고리즘을 적용해봤다.

fun main() {
    val input: MutableList<Int> = MutableList(readln().toInt()) { 0 }
    for (i in input.indices) { // 1
        input[i]= readln().toInt()
    }
    val countList: MutableList<Int> = MutableList(input.max()+1) { 0 }
    for (i in input.indices) { // 2
        countList[input[i]] += 1
    }
    for(i in 1..<countList.size){ // 3
        countList[i]+=countList[i-1]
    }
    val result: MutableList<Int> = MutableList(input.size) { 0 }
    for (i in input.size - 1 downTo 0) { // 4
        result[countList[input[i]]-1] = input[i]
        countList[input[i]] -= 1
    }
    println(result.joinToString(" "))
}

하지만 어림도 없지.. 메모리 초과!

사실 코드 짜면서 메모리, 시간 초과 날거같긴 했음..하핫

메모리 초과가 난 걸 보고 저걸 어찌해야할까 고민하였다.

 

우선 입출력에 대한 최적화는 BurfferReader와 BufferWriter를 사용함.

 

그리고

계수 정렬은 총 3개의 배열을 이용하는데 간단히 설명하자면

A 배열 : 기존 배열

B 배열 : A의 배열에서 원소의 등장 횟수에 대한 정보를 저장할 배열 (size = A의 최댓값+1, index = A의 원소값)

C 배열 : 정렬된 배열

이렇게다.

 

B에 저장된 등장횟수들을 누적합으로 바꿔줌 -> A를 뒤에서부터 접근하여 C[A[B[i]]] = A[i] 로 정렬하는 건데..

나는 이부분을 생략해도 된다고 생각했다.

B의 index는 A의 원소값이고, B의 원소는 등장 횟수이니..

애초에 B에 누적합 이런거 할 필요 없이 그냥 B를 돌면서 해당 원소값만큼 인덱스를 출력시키면 되지 않나..?

 

하지만 B의 크기는 결국 기존 배열의 최댓값에 의해 주어지는 등의 문제때문에 메모리,시간 초과는 계속 나서 전부 혼자서 풀진 못했다........ㅜㅠㅜㅠㅜㅜㅠ

fun main() {
    val count = IntArray(10_001)

    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    for(i in 1..br.readLine().toInt()){
        count[br.readLine().toInt()]++
    }
    for(i in 1..10_000){
        repeat(count[i]){
            bw.write("$i")
            bw.newLine()
        }
    }
    bw.flush()
    br.close()
    bw.close()
}

---

후기

사실 백준 3일차임...

코틀린도 덜 익숙해졌다고 느껴져서 기본적인 문제들로 손풀기 하는 중!

그러다 드디어 정렬을 만났는데 메모리, 시간초과.. 캬아악

화가나서 정리해본다..

추후에 계수정렬에 내용을 정리해서 올려야겠당

작심삼일이 되질 않길..

 

문제 링크