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

 

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

1920번: 수 찾기

 

---

 

문제 설명

간단한 이분탐색을 하는 문제이다. 수들의 존재여부만 판단하면 되기 때문에 간단하다.

 

코드

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int a[] = new int[n];

		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}

		Arrays.sort(a);

		int m = sc.nextInt();

		for (int i = 0; i < m; i++) {
			if (binarySearch(a, sc.nextInt()) >= 0) {
				System.out.println(1);
			} else {
				System.out.println(0);
			}
		}
	}

	static int binarySearch(int[] arr, int key) {
		int left = 0, right = arr.length - 1;

		while (left <= right) {
			int mid = (left + right) / 2;

			if (arr[mid] > key) {
				right = mid - 1;
			} else if (arr[mid] < key) {
				left = mid + 1;
			} else {
				return mid;
			}
		}

		return -1;
	}
}

 

코드 설명

일단 기본적으로 binarySearch 즉, 이분 탐색을 하는 코드를 사용한다.

처음에는 브루트포스로 하였는데, 디버깅을 하다가 시간이 너무 느려서 이분탐색으로 하였다. (시간 제한 1초)