[BOJ] 10815번 숫자 카드 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int n, m;
	static int[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		st= new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);

		m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < m; i++) {
			sb.append(binarySearch(Integer.parseInt(st.nextToken()))).append(" ");
		}
		System.out.println(sb.toString());
	}
	
	static int binarySearch(int key) {
		int start = 0;
		int end = arr.length - 1;
		
		while (start <= end) {
			int mid = (end + start) / 2;
			if (arr[mid] < key) {
				start = mid + 1;
			} else if (key < arr[mid]) {
				end = mid - 1;
			} else {
				return 1;
			}
		}
		return 0;
	}
}

📄 해설

• N 개의 수를 배열에 저장하고, M 개의 수를 입력받아 이진탐색을 수행
• 배열에 숫자가 존재하면 1을, 아니면 0을 반환하도록 이진탐색을 구현
• 수행 속도를 빠르게 하기 위해 Scanner 와 출력메소드를 사용하지 않고, BufferedReader 와 StringBuilder 를 사용하여 해결
• 메모리와 시간측면에서 매우 큰 차이를 보임