[백준] 18110 (solved.ac)

#1 알고리즘

힙 정렬 (Heap Sort)

힙 정렬을 사용했다. 힙 정렬 대신 병합 정렬을 사용할 수도 있다.

 

#2 여담

문제는 쉬워보이는데, 2024년 1월 8일 기준 정답률이 26퍼센트 밖에 되지 않는다. 그래서 문제를 풀기 전에 함정이 숨어있나싶었다. 그런 건 없었다. 문제의 이름이 solved.ac라서 사람들의 관심을 샀나보다. 그리곤 그 사람들이 그대로 가볍게 코드 제출을 해본 게 아닐까? 문제의 조건 자체는 쉽지만, 시간 초과가 나지 않게 하기 위한 빠른 정렬 기법 그리고 0으로 나누는 상황이 나오지 않게 만드는 처리를 요구한다.

 

#3 코드 - 코틀린

import kotlin.math.roundToInt

fun main() {
    // 점수 입력 받기
    val scoreCount = readln().toInt()
    val scores = Array(scoreCount) {0}
    for(i: Int in 0..<scoreCount) {
        scores[i] = readln().toInt()
    }

    // 점수 정렬
    heapSort(scores, 0, scores.size - 1)

    // 위, 아래 각각 절삭할 점수의 갯수
    val cutCountFromTopOrBottom : Int = (scoreCount.toDouble() * 0.15).roundToInt()

    // 절삭된 점수를 제외한 점수를 추려내기 위해 관련 변수를 미리 선언
    val scoreCountToAdd = scoreCount - (2 * cutCountFromTopOrBottom)
    val startIndexToAdd = cutCountFromTopOrBottom
    val endIndexToAdd = startIndexToAdd + scoreCountToAdd - 1

    // 합계 구하기
    var sum = 0
    for(i: Int in startIndexToAdd..endIndexToAdd) {
        sum += scores[i]
    }

    // 평균 점수 구하기
    val submitValue = if(scoreCountToAdd == 0) {0} else {(sum.toDouble() / scoreCountToAdd.toDouble()).roundToInt()}
    println(submitValue)
}

fun heapSort(array : Array<Int>, startIndex : Int, endIndex : Int) {
    val slicedArray = array.sliceArray(startIndex..endIndex)

    buildHeap(slicedArray)

    for(maxIndex : Int in (slicedArray.size - 1) downTo 1) {
        val temp = slicedArray[0]
        slicedArray[0] = slicedArray[maxIndex]
        slicedArray[maxIndex] = temp

        heapify(slicedArray, 0, maxIndex - 1)
    }

    slicedArray.reverse()
    for(i : Int in 0..(slicedArray.size - 1)) {
        array[startIndex + i] = slicedArray[i]
    }
}

fun heapify(array: Array<Int>, rootIndex: Int, maxIndex: Int) {
    val left = (rootIndex * 2) + 1
    val right = (rootIndex * 2) + 2
    var smaller = -1

    if(right <= maxIndex) {
        if(array[left] < array[right]) {
            smaller = left
        } else {
            smaller = right
        }

    } else if(left <= maxIndex) {
        smaller = left

    } else {
        return
    }

    if(array[smaller] < array[rootIndex]) {
        val temp = array[smaller]
        array[smaller] = array[rootIndex]
        array[rootIndex] = temp

        heapify(array, smaller, maxIndex)
    }
}

fun buildHeap(array : Array<Int>) {
    val maxIndex = array.size - 1

    for(i : Int in (maxIndex / 2) downTo 0) {
        heapify(array, i, maxIndex)
    }
}