백준 1920 자바(java) 수 찾기

문제

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

 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr = new int[sc.nextInt()];
		for(int i = 0; i<arr.length; i++) {
			arr[i] = sc.nextInt();
		}
		int[] checkArr = new int[sc.nextInt()];
		int count = 0;
		for(int i = 0; i<checkArr.length; i++) {
			if(check(arr, checkArr[i] = sc.nextInt()) == true){
				System.out.println("1");
			}
			else {
				System.out.println("0");
			}
		}
	}
	static boolean check(int[] arr, int checkArr) {
		for(int i =0; i<arr.length; i++) {
			if(arr[i] == checkArr) {
				return true;
			}
		}
		return false;
	}
}

 

위와 같은 for문을 이용해 하나하나 비교하는 방법으로 하려니 시간초과가 당연하게 발생하여

이분탐색의 방법을 사용하였다.

 

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

public class Main {
	static int n;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int[] arrN = new int[n];
		for(int i = 0; i<arrN.length; i++) {
			arrN[i] = sc.nextInt();
		}
		
		int m = sc.nextInt();
		int[] arrM = new int[m];
		for(int i = 0; i<arrM.length; i++) {
			arrM[i] = sc.nextInt();
		}
		
		Arrays.sort(arrN);
		
		for(int i = 0; i<arrM.length; i++) {
			if(check(arrN,arrM[i])) {
				System.out.println("1");
			}
			else {
				System.out.println("0");
			}
		}
	}
	static boolean check(int[] arrN, int arrM) {
		int first = 0;
		int last = arrN.length-1;
		int mid;
		while(first<=last) {
			mid = (first+last)/2;
			if(arrN[mid] == arrM) {
				return true;
			}
			if(arrM<arrN[mid]) {
				last = mid - 1;
			}
			else {
				first = mid+1;
			}
		}
		return false;
	}
}

자바로 이분탐색메소드를 직접 만들고 나서 해답들을 보니 Collections.binarySearch 라는 컬렉션 메소드가 존재하였다. 하지만 이분탐색의 알고리즘을 공부하는 좋은 기회였다.