문제

백준 1920번
https://www.acmicpc.net/problem/1920

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

Code

• 초기 상태(N = 5, arr = [4, 1, 5, 2, 3], M = 5, nums = [1, 3, 7, 9, 5])

• num = 1일 경우

• num = 3일 경우

• num = 7일 경우

• 3번째까지만 진행했지만, 위와 같이 반복한 결과 아래와 같은 결과를 얻을 수 있다.

Java

import java.util.*;
import java.io.*;

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());  // 정수의 개수
        arr = new int[N];
        StringBuilder sb = new StringBuilder();

        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());  // 존재 여부를 파악할 정수의 개수
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            // 이분 탐색을 통해 존재하면 True, 아니면 False
            if (binarySearch(Integer.parseInt(st.nextToken()))) {
                sb.append(1).append("\n");
            } else {
                sb.append(0).append("\n");
            }
        }
        System.out.println(sb);
    }

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

        while (left <= right) {
            // 큰 수 대비를 위한 방법
            int mid = left + (right - left) / 2;

            // arr 에 존재할 경우
            if (arr[mid] == num) {
                return true;
            }

            if (num > arr[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // while 문을 left > right 로 빠져나온 경우
        return false;
    }
}