백준 - 1920번: 수 찾기

문제

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

풀이

단순 이분 탐색 로직만 잘 구현한다면 쉽게 풀 수 있는 문제이다.

먼저 문제 이해를 해보면, 총 2개의 배열이 필요하다. 첫번째 배열은 N개의 정수를 저장할 수 있는 배열이 필요하고, 두번째 배열은 M개의 정수를 저장할 수 있는 배열이 필요하다.

N과 M개에 대한 입력 정보를 다 받았다면, M의 개수 만큼 반복을 순회하면서 해당 원소가 N개의 정수를 담은 배열에 존재하는지를 1, 0으로만 출력해주면 되는 문제이다.

이 과정을 순서대로 나열해보면

1. N과 N개의 정수를 입력받는다.
2. N개의 정수를 배열에 저장한다.
3. 2번 과정에서 저장한 정수들을 오름차순으로 정렬한다.
4. M과 M개의 정수를 입력받는다.
5. M개의 정수를 배열에 저장한다.
6. M의 크기 만큼 반복문을 순회하면서 5번 과정에서 저장한 정수들이 크기가 N인 배열에 존재하는지를 판단한다 (이분탐색 활용).
7. 있으면 1를 출력 없으면 0을 출력

소스 코드

/**
 * 1. N과 N개의 정수를 입력받는다.
 * 2. N개의 정수를 배열에 저장한다.
 * 3. 2번 과정에서 저장한 정수들을 오름차순으로 정렬한다.
 * 4. M과 M개의 정수를 입력받는다.
 * 5. M개의 정수를 배열에 저장한다.
 * 6. M의 크기 만큼 반복문을 순회하면서 5번 과정에서 저장한 정수들이 크기가 N인 배열에 존재하는지를 판단한다 (이분탐색 활용).
 * 7. 있으면 1를 출력 없으면 0을 출력
 */

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

public class Main {

	static int N, M;
	static int arrN[];
	static int arrM[];

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		arrN = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arrN[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arrN);

		M = Integer.parseInt(br.readLine());
		arrM = new int[M];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			arrM[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < M; i++) {
			System.out.println(binarySearch(arrN, arrM[i], 0, arrN.length - 1));
		}
	}

	private static int binarySearch(int[] arr, int target, int start, int end) {
		while (start <= end) {
			int mid = (start + end) / 2;

			if (arr[mid] == target) {
				return 1;
			} else if (arr[mid] < target) {
				start = mid + 1;
			} else if (arr[mid] > target) {
				end = mid - 1;
			}
		}
		return 0;
	}

}