[백준] 1920번. 수 찾기 (JAVA)

 

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

---

문제

---

풀이

 

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner kb = new Scanner(System.in);
		StringBuffer pr = new StringBuffer();
		int n = kb.nextInt();
		int[] arrN = new int[n];
		for(int i=0; i<n; i++) {
            arrN[i] = kb.nextInt();
        }
		
		int m = kb.nextInt();
		int[] arrM = new int[m];
		for(int i=0; i<m; i++) {
            arrM[i] = kb.nextInt();
        }
		
		Arrays.sort(arrN);
		
		for(int x : arrM) {
			int min = 0;
			int max = n-1;
			int answer = 0;
			while(min <= max) {
				int mid = (min + max) / 2;
				if(arrN[mid] == x) {
					answer = 1;
					break;
				}else if(arrN[mid] < x) {
					min = mid + 1;
				}else {
					max = mid - 1;
				}
			}
			pr.append(answer).append("\n");
			
		}
        
		
		
		System.out.print(pr);
        
       
        
    }
 
}

 시간 제한만 없다면 문제를 푸는데 전혀 어려움은 없을 것이다. 가장 대표적인 것은 ArrayList로 받은 다음 contains 메소드를 사용하면 된다. 이 경우 순차 탐색으로 시간이 오래 걸린다는 단점을 가지고 있다. 실제로 이렇게 풀면 시간 초과가 나오며 틀리게 된다.

 탐색에서 시간을 줄일 수 있는 방법은 이분 탐색(Binary Search)을 하는 것이다. 이분 탐색을 구현만 해주면 전혀 어려운 문제는 아니었다.