(JAVA) 백준 1920번 : 수 찾기

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

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

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

---

예전에 단순하게 선형 검색 방법으로 시도했다가 실패하고,

알고리즘 수업 때 배운 이진 탐색을 복습하면서 적용했더니 풀린 문제.

다 풀고 보니까 N 배열을 만들고 따로 정렬하는데 시간이 좀 더 걸린 느낌인데 더 빠른 방법이 없는지 궁금하다.

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

public class B_1920 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        String[] data = br.readLine().split(" ");
        int M = Integer.parseInt(br.readLine());
        String[] data2 = br.readLine().split(" ");
        ArrayList<Integer> list = new ArrayList<Integer>(N);
        for (String i : data) {
            list.add(Integer.parseInt(i));
        }
        Collections.sort(list);
        for (String i : data2) {
            bw.write(String.format("%d%n", BynarySearch(list, Integer.parseInt(i))));
        }
        bw.flush();
        bw.close();
    }    
    static int BynarySearch (ArrayList<Integer> a, int key) {
        int left = 0;
        int right = a.size()-1;
        do {
            int center = (left+right)/2;
            if (a.get(center)==key) {
                return 1;
            }
            else if(a.get(center)<key) {
                left = center+1;
            }
            else {
                right = center-1;
            }
        }
        while (left<=right);
        return 0;
    }
}