(Java) 백준 1920 : 수 찾기

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

 

N개의 정수를 요소로 하는 배열을 M번 탐색하는 문제

 

순차탐색 : 시간복잡도 O(N * M) = 100억. 시간제한 1초당 1억 연산 횟수 정도로 보기 때문에 시간 제한에 걸린다.

이진탐색: 시간복잡도 O(M * logN)

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

public class Main {

	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int[] intArr1 = new int[n];
		
		for(int i=0; i<n; i++) {
			intArr1[i] = scanner.nextInt();
		}//for end
		
        	//이진탐색 전 배열을 반드시 정렬해야한다!
		Arrays.sort(intArr1);
		
		int m = scanner.nextInt();
		int[] intArr2 = new int[m];
		
		for(int i=0; i<m; i++) {
			intArr2[i] = scanner.nextInt();
		}//for end
		
		for(int j=0; j<m; j++) {
			System.out.println(binarySearch(intArr1, intArr2[j]));
		}//for end
	}//main() end
	
	static int binarySearch(int[] intArr, int key) {
		int pl = 0;
		int pr = intArr.length-1;
		
		while(pl<=pr) {
			int pc = (pl+pr)/2;
			if(intArr[pc]==key) {
				return 1;
			} else if(intArr[pc]>key) {
				pr = pc-1;
			} else {
				pl = pc+1;
			}
		}//while end
		
		return 0;
	}//binarySearch() end
}

 

binarySearch()를 직접 구현하지 않고, Arrays.binarySearch(배열, 키)를 사용해도 된다.