[Baekjoon] 10815 숫자 카드

✉️문제

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

10815번: 숫자 카드

 

📝 접근

   이분 탐색을 이용한다. 이분 탐색의 핵심은 left point와 right point를 선언한다음 이를 계속 업데이트하는 것이다.

 

🗝 문제풀이

package baekjoon;

import java.util.Arrays;
import java.util.Scanner;

public class B10815 {

    static int n,m;
    static int[] arr, answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt(); // 상근이가 가지고 있는 숫자 카드

        arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);

        m = sc.nextInt(); // m개의 숫자
        answer = new int[m];

        for(int i = 0; i < m; i++) {
            int input = sc.nextInt();
            solution(i, input);
        }

        for (int i : answer) {
            System.out.println(i);
        }
    }

    public static void solution(int idx, int target) {
        int lt = 0, rt = n - 1;
        int middle;
        while(lt <= rt) {
            middle = (lt + rt) / 2;
            if(arr[middle] == target) {
                answer[idx] = 1;
                return;
            }
            else if(arr[middle] > target) rt = middle - 1;
            else lt = middle + 1;
        }
    }
}