[JAVA] 백준 - 1920 수 찾기

이분탐색을 사용하는 문제다.

알고리즘 문제들을 풀며 느낀 것 중 하나인데

문제를 읽어보고 뭔가 완전 탐색을 진행해야 될 것 같은데

문제에서 주어지는 데이터의 범위가 엄청 크다면 -> 이분탐색

데이터의 범위가 작다면 -> 완전탐색

인 것 같다. 물론 모든 문제가 그렇지 않을 것이고 그냥 개인적인 느낌이다.

 

🤔 문제 접근

주어진 M개의 데이터가 N개의 숫자 중 존재하는지 확인하면 되는 문제다.

문제를 보고 N개의 숫자 데이터를 ArrayList에 담은 뒤

contains 메서드를 이용해 풀고자 했지만 시간초과가 났다.

그 이유는 contains 메서드는 데이터 n개 내에서 A라는 데이터가 존재하는지 

확인 할 때 n개 데이터 전체를 완전 탐색하기 때문에 

최악의 경우 작업 횟수가 n*m 번 진행된다.

따라서 이번 문제에 경우 N의 최대 범위가 100,000 이고

M의 최대 범위도 100,000 이므로 1초의 시간제한을 초과하는 것이다.

마찬가지로 완전 탐색도 불가능하다.

 

✅ 핵심 풀이

데이터 범위가 매우 크므로 이분탐색을 활용하자.

이분탐색의 시간 복잡도는 logN으로

현재 문제에서는최악의 경우

m*logN -> 100,000 * log100,000 -> 100,000 * 5 만큼 작업을 수행하므로

시간제한 1초를 넘지 않게 된다.

 

🚨 CODE

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<m; i++) {
			
			int num = Integer.parseInt(st.nextToken());
			sb.append(bs(arr, num)).append("\n");
		}
		System.out.println(sb);
		
		
	}
	public static int bs(int[] arr, int num) {
		int start = 0;
		int end = arr.length-1;
		
		while(start <= end) {
			int mid = (start+end)/2;
			
			if(arr[mid] < num)
				start = mid+1;
			else if(arr[mid] > num)
				end = mid-1;
			else // arr배열에서 num을 찾은 경우
				return 1;
		}
		return 0; // 못 찾은 경우
		
	}
}