[Silver IV] 수 찾기 - 1920 - Kotlin

문제 링크

성능 요약

메모리: 91776 KB, 시간: 2012 ms

분류

이분 탐색(binary_search), 자료 구조(data_structures), 해시를 사용한 집합과 맵(hash_set)

문제 설명

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

---

풀이

• 가장 기본적인 이분 탐색이라고 생각한다. 비교할 값들을 배열로 만들고 하나씩 꺼내어 arr1에 존재하는지를 이분 탐색으로 보는 것이다.

• low와 high로 기본 인덱스를 맞춰주고 mid로 반을 나눠가면서 찾는다. 먼저 mid가 찾는 수가 맞는지 확인을 한다. 아니라면 우리가 찾는 범위를 좁히는 조건을 걸어준다.

• 만약 mid 인덱스의 값이 내가 하나씩 꺼내어 가져온 비교값보다 크면 low와 mid 사이에 찾는 수가 있으므로 high에 mid-1 을 넣어주고 다시 검사한다. 또는 비교값보다 작으면 반대로 low를 mid+1로 범위를 맞춰 다시 검사한다.

• 만약 찾지 못할 경우는 결국 while의 조건인 (low <= high)에 걸리고 0이 반환된다.

답

fun main() {
    val N = readln().toInt()
    val arr1 = readln().split(" ").map { it.toInt() }.sorted()
    val M = readln().toInt()
    val arr2 = readln().split(" ").map { it.toInt() }
    arr2.forEach { println("${binary(arr1,it)} ") }
}
fun binary(arr1: List<Int>, findNum: Int) : Int {
    var low = 0
    var high = arr1.size-1
    var mid: Int;
    while(low <= high) {
        mid = (low + high) / 2
        if(findNum == arr1[mid]) { return  1 }
        else if(findNum < arr1[mid]) { high = mid - 1 }
        else low = mid + 1
    }
    return 0
}

이는

[Silver V] 숫자 카드 - 10815 (문제 링크) - https://github.com/delvering17/Study_BAEKJOON/tree/main/백준/Silver/10815. 숫자 카드
[Silver V] CD - 4158(문제 링크) - https://github.com/delvering17/Study_BAEKJOON/tree/main/백준/Silver/4158. CD
와도 같은 방식으로 풀 수 있다.