[백준/BOJ] 10815번: 숫자 카드, 1920번: 수 찾기

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

10815번: 숫자 카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

해설

이중 반복문을 실행하거나 contains 함수를 이용하여 문제를 풀 수 있지만 시간 초과가 발생하게 된다.

이를 해결하기 위해 이진 탐색을 이용하였다.

코드를 보며 이해해보고 잘 이해가 되지 않는다면 이진 탐색에 대해 검색해 보는 것을 추천한다.

소스 코드

import java.lang.StringBuilder
import java.util.*

fun main() {
    val sb = StringBuilder()
    val n = readLine()!!.toInt()
    val arrayA = Array(n) { 0 }
    var st = StringTokenizer(readLine())
    for(i in 0 until n) arrayA[i] = st.nextToken().toInt()
    arrayA.sort()
    val m = readLine()!!.toInt()
    st = StringTokenizer(readLine())
    for(i in 0 until m) {
        val card = st.nextToken().toInt()
        var low = 0
        var high = n - 1
        var searched = false
        while(low <= high) {
            val mid = (low + high) / 2
            if(arrayA[mid] == card) {
                searched = true
                break
            }
            else if(arrayA[mid] < card) low = mid + 1
            else high = mid - 1
        }
        if(!searched) sb.append("0 ")
        else sb.append("1 ")
    }
    println(sb.toString())
}

 

※ 1920번: 수 찾기도 똑같이 풀면 된다.