[백준] 10816번 - 숫자 카드 2

 

이 문제는 바이너리 서치를 이용한 문제이다. 바이너리 서치를 쉽게 설명하자면 정렬되어 있는 배열의 총 인덱스의 중간 지점부터 시작하여 원하는 값이 더 크면 중간지점에서부터 끝까지, 그렇지 않으면 처음부터 중간지점까지 가는 방식으로 값을 찾아가는 탐색 방식이다. 바이너리 서치를 사용하는 이유는 시간복잡도를 O(logn)이므로 효율적인 알고리즘이기 때문이다.

바이너리 서치를 이용하여 원하는 값이 처음 등장하는 부분과 마지막으로 등장하는 부분을 찾아서 그 숫자의 차를 출력해주는 방식으로 문제를 해결할 수 있다.

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

public class p10816 {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int a = Integer.parseInt(br.readLine());
		int[] ary = new int[a];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < a; i++) {
			ary[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(ary);
		int b = Integer.parseInt(br.readLine());

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < b; i++) {
			int k = Integer.parseInt(st.nextToken());
			sb.append(max(k, ary) - min(k, ary) + " ");
		}
		System.out.println(sb);
	}

	public static int min(int a, int[] ary) {
		int start = 0;
		int end = ary.length;
		int mid;

		while (start < end) {
			mid = start + (end - start) / 2;
			if (a <= ary[mid]) {
				end = mid;
			} else {
				start = mid + 1;
			}
		}
		return start;
	}

	public static int max(int a, int[] ary) {
		int start = 0;
		int end = ary.length;
		int mid;

		while (start < end) {
			mid = start + (end - start) / 2;
			if (a >= ary[mid]) {
				start = mid + 1;
			} else {
				end = mid;
			}
		}
		return start;
	}
}