[백준] 11399 (ATM)

#1 알고리즘

#1-1

병합 정렬 (Merge Sort)

우선 손님 별 돈을 인출하는 시간들을 정렬해야 한다. 이 문제에서는 병합 정렬을 사용했다.

 

#1-2

1번 열 + 2번 열 + 3번 열 + ... + personCount번 열로 모든 손님들의 대기 시간 총합을 구한다.

 

#2 코드 - 코틀린

fun main() {
    val personCount = readln().toInt()
    
    val timeStrings = readln().split(" ")
    val times : Array<Int> = Array(personCount) {0}
    for(i : Int in 0..<personCount) {
        times[i] = timeStrings[i].toInt()
    }
    
    mergeSort(times, 0, times.size - 1)
    
    var timeSum = 0
    /* (1) 첫번째 손님이 인출하는데 걸리는 시간 = times[0]
     * (2) 두번째 손님이 인출하는데 걸리는 시간 = times[1] + times[0]
     * ...
     * (personCount - 1) 마지막 손님이 인출하는데 걸리는 시간 = times[personCount - 1] + ... + times[1] + times[0]
     * (1)부터 (personCount -1)까지 더한 값을 print한다.
     */
    for(i : Int in 0..<personCount) {
        timeSum += times[i] * (personCount - i)
    }
    
    println(timeSum)
}

fun mergeSort(array: Array<Int>, startIndex : Int, endIndex : Int) {

    // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
    if(startIndex < endIndex) {
        val midIndex = (startIndex + endIndex) / 2
        mergeSort(array, startIndex, midIndex)
        mergeSort(array, (midIndex + 1), endIndex)

        merge(array, startIndex, midIndex, endIndex)
    }
}

fun merge(array : Array<Int>, startIndex: Int, midIndex : Int, endIndex: Int) {
    // array에서 나뉜 'f'irst 부분을 순회할 인덱스 f
    var f = startIndex // f의 최댓값은 midIndex

    // array에서 나뉜 's'econd 부분을 순회할 인덱스 s
    var s = midIndex + 1 // s의 최댓값은 endIndex

    // 'T'emporary 배열 그리고 이 배열을 순회할 인덱스 t
    val T : Array<Int> = Array(endIndex - startIndex + 1) { 0 }
    var t = 0

    while(f <= midIndex && s <= endIndex) {

        if(array[f] < array[s]) {
            T[t++] = array[f++]

        } else {
            T[t++] = array[s++]
        }
    }

    // f의 영역이 남았다면 비워준다
    while(f <= midIndex) {
        T[t++] = array[f++]
    }

    // s의 영역이 남았다면 비워준다
    while(s <= endIndex) {
        T[t++] = array[s++]
    }

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