[백준 / 자바] 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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

5 // 데이터 개수
4 1 5 2 3
5 // 찾아야할 숫자 개수
1 3 7 9 5

 

출력

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

1
1
0
0
1

 

풀이

데이터셋 크기 최대 100,000 → O(n^2) 불가

이진탐색을 적용 → O(NlogN) 시간복잡도 가능

자바의 기본 정렬필요 → O(NlogN)

→ 2NlogN으로 상수는 무시됨 O(NlogN)의 시간복잡도

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine()); // 데이터의 개수
        int[] data = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            data[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(data); // 오름차순으로 정렬

        int m = Integer.parseInt(br.readLine()); // 찾을 데이터 수
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            boolean find = false;
            int target = Integer.parseInt(st.nextToken()); // 찾을 데이터

            // 이진 탐색 시작
            int start = 0;
            int end = data.length - 1;
            while (start <= end) {
                int midi = (start + end) / 2;
                int midV = data[midi];
                if (midV > target) {
                    end = midi - 1;
                } else if (midV < target) {
                    start = midi + 1;
                } else {
                    find = true;
                    break;
                }
            }
            if(find) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
    }
}