[백준][Kotlin]1920번 수 찾기

해당 문제는 이진탐색을 사용하면 풀 수 있는 문제였습니다.

이진탐색은 간단히 설명하자면 최소값과 최대값을 중간값과 원하는 결과값의 대소비교를 하여 최소값과 최대값을 변경하면서 최적의 해를 찾는 방법입니다.

그리고 이진탐색으로 해당 문제를 작성하였습니다.

하기는 이진탐색으로 작성한 코드와 제출 결과 입니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Math.max
import java.util.*
import kotlin.collections.ArrayList

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    var N = st.nextToken().toInt()
    var arr = IntArray(N){0}
    st = StringTokenizer(br.readLine())
    repeat(N){
        arr[it] = st.nextToken().toInt()
    }
    Arrays.sort(arr) // 배열 정렬
    st = StringTokenizer(br.readLine())
    val M = st.nextToken().toInt()
    st = StringTokenizer(br.readLine())
    repeat(M){
        val find = st.nextToken().toInt() // 찾아야 할 값
        var start = 0 // 시작 지점
        var end = N-1 // 끝나는 지점
        var check = false
        while(start <= end){
            val mid = (start+end)/2
            if(arr[mid] < find){
                start = mid+1
                continue
            }
            if(arr[mid] > find){
                end = mid-1
                continue
            }
            if(arr[mid] == find){
                check = true
                break
            }
        }
        if(check){
            bw.appendLine("1")
        } else {
            bw.appendLine("0")
        }
    }
    bw.flush()
    bw.close()
}

 

 

그리고 해당 글을 작성하면서 HashMap와 HashSet의 검색속도는 O(1) 이라는 사실이 생각이나서 HashSet을 사용하여 추가로 작성해 보았습니다.

하기는 HashSet 을 사용하여 작성한 코드와 제출 결과 입니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Math.max
import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashSet

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    var N = st.nextToken().toInt()
    var arr = HashSet<Int>()
    st = StringTokenizer(br.readLine())
    repeat(N){
        arr.add(st.nextToken().toInt())
    }

    st = StringTokenizer(br.readLine())
    val M = st.nextToken().toInt()
    st = StringTokenizer(br.readLine())
    for(i in 1 .. M){
        val find = st.nextToken().toInt() // 찾아야 할 값
        if(arr.contains(find)){
            bw.appendLine("1")
            continue
        }
        bw.appendLine("0")
    }
    bw.flush()
    bw.close()
}