[백준] 1920 (수 찾기)

#1 알고리즘

#1-1

이진 탐색 (Binary search)

시간 초과가 뜨지 않게 하기 위해서 배열에 이진 탐색을 수행한다. 
 

#1-2

힙 정렬 (Heap Sort)

이진 탐색을 수행하려면 먼저, 배열이 정렬되어있어야 한다. 나는 이 문제을 힙 정렬을 이용해 정렬했다.
 

#2 여담

문제 자체는 굉장히 간단하다. 대신 빠른 정렬과 검색 기법에 대한 지식을 요구한다.
 

#3 코드 - 코틀린

fun main() {
    val N = readln().toInt()
    val stringOfA = readln().split(" ")
    val A = Array(N) {0}
    for(i: Int in 0..<N) {
        A[i] = stringOfA[i].toInt()
    }
    val M = readln().toInt()
    val stringOfB = readln().split(" ")
    val B = Array(M) {0}
    for(i: Int in 0..<M) {
        B[i] = stringOfB[i].toInt()
    }
    
    heapSort(A, 0, A.size - 1)
    
    for(b in B) {
        if(binarySearch(A, b) == -1) {
            println(0)
        } else {
            println(1)
        }
    }
}

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)
    }
}

fun binarySearch(values : Array<Int>, x : Int) : Int {
    var min = 0
    var max = values.size - 1

    while(min <= max) {
        val mid = (min + max) / 2

        // up
        if(values[mid] < x) {
            min = mid + 1
        
        // equal
        } else if(values[mid] == x) {
            return mid

        // down
        } else { // values[mid] > x
            max = mid - 1
        }
    }

    return -1
}