[백준 2805] 나무 자르기 -JAVA // le_effort

수 찾기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	76528	23584	15459	30.149%

문제

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

예제 입력 1 복사

xxxxxxxxxx
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 복사

xxxxxxxxxx
1
1
0
0
1

출처

 

 

풀이

N이 최대 10만

M이 최대 10만이니

 

N^2 로 비교하면 시간초과가 난다.

 

그래서 logN의 시간복잡도를 가지고있는 이분탐색을 통해서 풀었다.

 

xxxxxxxxxx
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static ArrayList<Integer>list = new ArrayList<>();
    static ArrayList<Integer>comp = new ArrayList<>();
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        
        int n = Integer.parseInt(br.readLine());
        
        String [] input = br.readLine().split(" ");
        
        for(int i=0; i<n; i++) {
            list.add(Integer.parseInt(input[i]));
        }
        
        int m =Integer.parseInt(br.readLine());
        
        input = br.readLine().split(" ");
        for(int i=0; i<m; i++) {
            comp.add(Integer.parseInt(input[i]));
        }
        
        
        Collections.sort(list);
        
        
        for(int i=0; i<m; i++) {
            boolean flag = false;
            int num = comp.get(i);
            
            int start = 0;
            int end = n-1;
            
            while(start <= end) {
                int mid = (start+end)/2;
                if(list.get(mid)==num) {
                    flag = true;
                    System.out.println(1);
                    break;
                }
                
                if(list.get(mid) > num) {
                    end = mid-1;
                }
                else {
                    start = mid+1;
                }
            }
            if(!flag) {
                System.out.println(0);
            }       
        }   
    }
}
​