[BOJ] 1920. 수 찾기 - (Java)

[BOJ] 1920. 수 찾기 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 20M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/11650

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

Input

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

Output

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

Example

input

5
4 1 5 2 3
5
1 3 7 9 5

output

1
1
0
0
1

Solution & Inpression

정렬 후 이분탐색

Code

언어 : JAVA

메모리 : 170092 kb

실행 시간 : 1164 ms

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

public class Main {
    static int N;
    static int[] data;

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

        for (int i = 0; i < N; i++) {
            data[i] = sc.nextInt();
        }

        Arrays.sort(data);

        int M = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            if (find(sc.nextInt()))
                sb.append("1\n");
            else
                sb.append("0\n");
        }
        System.out.println(sb);
    }

    private static boolean find(int x) {
        int s = 0, e = N, m = 0;
        while (s < e) {
            m = (s + e) >> 1;
            if (data[m] == x)
                return true;
            else if (data[m] > x) {
                e = m;
            } else {
                s = m + 1;
            }
        }

        return false;
    }
}