[백준] 1920번: 수 찾기 - Kotlin[코틀린]

문제

 

1920번: 수 찾기

 

---

풀이

 

 이 문제를 풀이하기 위해 이분 탐색(Binary Search) 알고리즘이 필요하다. 이분 탐색이란 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간값을 선택하고, 찾고자하는 값과 비교해서 중간값이 더 크다면 그 중간값이 새로운 최댓값이 되고, 더 작다면 최솟값이 된다. 그리고 다시 새로운 중간값을 찾고, 찾고자하는 값과 비교해나가는 것이다.

이미지 출처 - 위키 백과

 풀이한 코드에서는 binarySearch 함수의 return 값을 Boolean으로 정하고, 찾고자 하는 값을 찾았다면 true 아니라면 false를 return 하도록 하였다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val sb = StringBuilder()

    val size = br.readLine().toInt()
    val arr = br.readLine().split(' ').map { it.toInt() }.toIntArray() // 주어진 정수
    arr.sort()

    val num = br.readLine().toInt()
    val line = br.readLine().split(' ').map { it.toInt() }.toIntArray() // 찾으려는 정수

    line.forEach {
        if(binarySearch(arr, it)) {
            sb.append(1).append('\n')
        } else {
            sb.append(0).append('\n')
        }
    }

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}

fun binarySearch(arr: IntArray, key: Int) : Boolean { // arr: 입력받은 숫자, key : 찾으려는 값
    var lo = 0
    var hi = arr.size - 1

    while (lo <= hi) {
        val mid = (lo+hi) / 2

        if(arr[mid] == key) {
            return true
        } else if (arr[mid]> key) { // mid가 key보다 크다면 mid가 새로운 최댓값이 된다.
            hi = mid - 1
        } else { // mid가 key보다 작다면 mid가 새로운 최솟값이 된다.
            lo = mid + 1
        }
    }

    return false
}