수 찾기 (백준 1920)

1초

128 MB

문제

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을 출력한다.

 

---

<생각의 흐름>

N이랑 M의 최대가 100000이라 O(n^2)보다는 빠른 알고리즘 필요할듯??
이진 탐색을 적용하면 O(nlogn) 시간복잡도로 해결할 수 있음
이진 탐색은 정렬을 가정하므로 정렬 함수도 사용합니다 (자바의 기본정렬도 가능)

이 문제에서는 O(MlogN)임

 

<코드>

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

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] A = new int[N];
        for(int i = 0 ; i < N ; i++){
            A[i] = sc.nextInt();
        }
        Arrays.sort(A);

        int M = sc.nextInt();
        for(int i = 0 ; i < M ; i++){
            boolean find = false;
            int target = sc.nextInt();
            int start = 0;
            int end = A.length -1;
            while(start <= end){
                int mid_index = (start+end)/2;
                int mid_value = A[mid_index];
                if(mid_value > target){
                     end = mid_index-1;
                }else if(mid_value < target){
                    start = mid_index + 1;
                }else{
                    find = true;
                    break;
                }
            }
            if(find) System.out.println(1);
            else System.out.println(0);

        }

     }
}

---

<피드백>

이진 탐색 하는 방법 숙지 (쉬움 )