[Kotiln] BOJ1920 수 찾기

그냥 시간 복잡도 계산해서 좌우 Pivot잡아서 풀었었는데

이진 탐색 으로도 풀 수 있는 문제였다.

아래 이진탐색 코드도 첨부

 

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

1920번: 수 찾기

#Pivot 풀이

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt() //1~ 10만
    val inputs = br.readLine().split(" ").map {it.toInt()}.toMutableList()
    val M = br.readLine().toInt() //1~10만
    val checkList = br.readLine().split(" ").mapIndexed { index, s -> Pair(index,s.toInt()) }.toMutableList()
    val answer = Array(M){0}
    //그냥 선형탐색 하면 N^2으로 최대 1000억까지 나옴으로 시간초과
    //==> 사전 정렬 후 탐색

    inputs.sort() //NlogN
    checkList.sortBy { it.second } //NlogN

    var inputsPivot = 0; var checkListPivot = 0

    while (true){ //2N
        if ((inputsPivot > inputs.lastIndex) || (checkListPivot > checkList.lastIndex)) break

        //값이 같으면 checkListPivot 증가
        if (inputs[inputsPivot] == checkList[checkListPivot].second){
            answer[checkList[checkListPivot].first] = 1
            checkListPivot++
        //값이 다르면 값이 작은쪽 Pivot 증가 (answer에 0저장)
        }else{
            if (inputs[inputsPivot] > checkList[checkListPivot].second){
                checkListPivot++
            }else{
                inputsPivot++
            }
        }
    }

    answer.forEach { println(it) }
}

#이진 탐색 풀이

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt() //1~ 10만
    val inputs = br.readLine().split(" ").map {it.toInt()}.toMutableList()
    val M = br.readLine().toInt() //1~10만
    val checkList = br.readLine().split(" ").mapIndexed { index, s -> Pair(index,s.toInt()) }.toMutableList()
    val answer = Array(M){0}

    inputs.sort() //NlogN
    checkList.sortBy { it.second } //NlogN

    checkList.forEach { //logN
        val returnIndex = inputs.binarySearch(it.second)
        if (returnIndex >= 0) answer[it.first] = 1
    }
    answer.forEach { println(it) }
}

.binarySearch()

찾는 원소가 존재한다면 해당 원소의 index값을 return

찾는 원소가 없다면 음수를 return  ==> 음수값  =  - (원래 있어야할 위치) - 1