[JAVA]백준 1920번: 수 찾기

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

1920번: 수 찾기

1. 문제 설명

 

N개의 정수 A [1], A [2].. A [N]가 주어진다.

M개의 정수가 주어질 때, 이 수 들이 A[] 안에 존재하는지 알아낸다.

 

1 <=N <=100,000

1 <=M <=100,000

 

2. 풀이

 

이진 탐색으로 풀 수 있는 문제이다.

 

완전 탐색으로 풀게 되면 N과 M의 값 때문에 시간 초과가 발생한다.

 

완전 탐색의 경우 N*M번의 연산을 수행하고 최악의 경우 100,000*100,000 = 10,000,000,000 연산을 수행함으로 2초 안에 문제를 해결할 수 없다.

 

이진 탐색으로 값을 찾고, 있을 경우 1 없을 경우 0을 출력하면 된다.

 

 

3. 코드

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

public class Main {

    public static int N, M;
    public static int[] list;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        // N만큼 배열 생성
        list = new int[N];

        // N개의 정수 입력

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int x = 0; x < N; x++) {
            list[x] = Integer.parseInt(st.nextToken());
        }

        // 정렬

        Arrays.sort(list);


        // 배열 안에 들어 있는지 확인
        M = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());

        for (int x = 0; x < M; x++) {
            int now = Integer.parseInt(st.nextToken());

            if (binarySearch(now)) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }

        }

        System.out.println(sb);

    }

    // 이진 탐색
    public static boolean binarySearch(int x) {
        int left = 0;
        int right = N - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (list[mid] < x) {
                left = mid + 1;
            } else if (list[mid] > x) {
                right = mid - 1;
            } else {
                return true;
            }
        }


        return false;
    }


}