[백준 1920][Kotlin] 수 찾기

문제 링크

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

코드

fun main() {  
    val n = readln().toInt()  
    val list = readln().split(' ').map{it.toInt()}.sorted()  // 이진 탐색을 위해 오름차순 정렬
    val m = readln().toInt()  
    val itemList = readln().split(' ').map{it.toInt()}  
  
    for (i in 0 until m) {  // 이진 탐색
        var low = 0  
        var high = n-1  
        var mid: Int = 0  
        var valid = false  
        while (low <= high) {  
            mid = (low+high)/2  
            when {  
                itemList[i] == list[mid] -> {  
                    valid = true  
                    break // 바깥 while에 적용됨
                }  
                itemList[i] > list[mid] -> {  
                    low = mid+1  
                }  
                else -> {  
                    high = mid-1  
                }  
            }  
        }  
  
        if (valid)  
            println("1")  
        else  
            println("0")  
    }  
}

설명

수를 하나씩 대소 비교하는 것은 O(N제곱)이 걸리는데 이는 시간제한(1초)를 초과하므로 리스트의 요소를 오름차순 정렬하고 이진탐색을 통해 풀었다.

후기

이진 탐색일 때 시간 복잡도는 O(logN)이다. 이를 기억하고 부루트포스와 이진탐색 중 하나를 결정하자. 사실 정렬만 O(N)로 할 수 있다면 수 대소 비교를 통한 탐색은 이진탐색으로 하는 것이 효율이 훨씬 좋다.