[백준]10815 숫자 카드

리스트에 담아서 그냥 가지고 있는지 체크해서 풀려고 했던 나 반성 .. 이 문제는 이진탐색을 이용해서 풀지 않으면 시간 초과가 났다
순차적 탐색은 최악의 경우 모든 수를 거쳐야하기 때문에 시간복잡도가 O(n)이지만 이분탐색은 탐색할때마다 반씩 줄어들기 때문에 시간복잡도가 O(log N)이 된다!
우리 업다운 게임할때 100이면 50, 25 이렇게 반으로 뚝뚝 끊어서 물어보는 것처럼 ~~!

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_10815 {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int M = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split(" ");
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(s[i]);
            if(binarySearch(num)) {
                sb.append("1 ");
            } else {
                sb.append("0 ");
            }
        }
        System.out.println(sb.toString());

    }

    public static boolean binarySearch(int num) {
        int left = 0;
        int right = arr.length-1;
        int mid = 0;

        while(left <= right) {
            mid = (left + right) / 2;
            if (num > arr[mid]) {
                // 기준값보다 클 때 왼쪽 다 버림
                left = mid+1;
            } else if(num < arr[mid]) {
                // 기준값보다 작으면 오른쪽 다 버림
                right = mid-1;
            } else {
                return true;
            }
        }
        return false;
    }
}

코드는 쉽다! 알고리즘만 잘 이해하면..
이건 코틀린코드!

package baekjoon

import java.util.*

var arr = emptyArray<Int?>()

fun main() {
    val sb : StringBuilder = StringBuilder()

    val N = readLine()!!.toInt()
    arr = arrayOfNulls(N)


    val st : StringTokenizer = StringTokenizer(readLine())
    for (i in 0 until N) {
        arr[i] = st.nextToken().toInt()
    }
    Arrays.sort(arr)

    val M = readLine()!!.toInt()
    val s = readLine()!!.split(" ")
    for(i in 0 until M) {
        var num = s[i].toInt()
        if(binarySearch(num)) {
            sb.append("1 ")
        } else {
            sb.append("0 ")
        }
    }
    print(sb.toString())

}

fun binarySearch(num:Int) : Boolean {
    var left = 0
    var right = arr.size -1

    while(left <= right) {
        var mid = (left+right)/2
        if(num > arr[mid]!!) {
            left = mid+1
        } else if(num < arr[mid]!!) {
            right = mid-1
        } else {
            return true;
        }
    }
    return false;
}

의외로 이번 문제는 자바가 성능이 더 좋았다

print문 빼먹어서 한번 틀리고 시간 초과 때문에 한번 틀린거 빼면 성고옹 ~