[Java] 백준 1920번 : 수 찾기

문제

1920번: 수 찾기

---

 

접근 방법

1. 완전탐색으로 풀려다 보니 100,000^2 시간 초과가 발생할것 입니다. 그래서 투포인터로 풀었습니다.

 

코드

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

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N,M;
    private static int[] arrN;


    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

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

        arrN = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < N ; i++){
            arrN[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arrN);

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

        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < M ; i++){
            if(process(Integer.parseInt(st.nextToken()))){
                sb.append(1).append("\n");
            }else{
                sb.append(0).append("\n");
            }
        }
    }

    //실행
    public static boolean process(int input) {
        int s = 0;
        int e = N-1;

        while (s<=e){
            int mid = (s+e)/2;

            if(input < arrN[mid]){
                e = mid-1;
            }else if (input > arrN[mid]){
                s = mid+1;
            }else{
                return true;
            }
        }

        return false;
    }


    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
}