10816. 숫자 카드 2 (자바, Java)

이전문제 는 카드의 존재유무만 가렸다고 한다면, 이번 문제는 카드의 갯수를 구해야 하는 문제다.

역시나 마찬가지로 브루트 포스를 통하면 해결할 수는 있겠으나, 별 의미가 없어서

구글링으로 찾아보았다. 같은 값을 가진 방법을 세는 lowerbound와 upperbound에 대해 알게되었고,

양쪽의 차이를 빼줘서 갯수를 구할 수 있었다.

 

이전에 썼던 코드에서 조금만 추가하면 됐기에, 다소 수월하게 코딩할 수 있었다.

 

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[] ncard;

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

		n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		ncard = new int[n];

		for (int i=0; i<n; i++) {
			ncard[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(ncard);

		m = Integer.parseInt(br.readLine());


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

		for (int i=0; i<m; i++) {
			int mcard = Integer.parseInt(st.nextToken());
			sb.append(binarySearch(mcard) + " ");
		}

		System.out.println(sb);

	}

	static int binarySearch(int mcard) {

		int lIndex = 0;
		int rIndex = ncard.length-1;

		while (lIndex <= rIndex) {
			int avg = (lIndex + rIndex) / 2;
			int mid = ncard[avg];

			if (mcard < mid) {
				rIndex = avg-1;
			} else if (mcard > mid) {
				lIndex = avg+1;
			} else {
				return (upperBound(mcard) - lowerBound(mcard));
			}
		}

		return 0;
	}

	static int lowerBound(int mcard) {

		int lIndex = 0;
		int rIndex = ncard.length-1;

		while (lIndex <= rIndex) {
			int avg = (lIndex + rIndex) / 2;
			int mid = ncard[avg];

			if (mcard <= mid) {
				rIndex = avg-1;
			} else if (mcard > mid) {
				lIndex = avg+1;
			}
		}

		return lIndex;

	}

	static int upperBound(int mcard) {

		int lIndex = 0;
		int rIndex = ncard.length-1;

		while (lIndex <= rIndex) {
			int avg = (lIndex + rIndex) / 2;
			int mid = ncard[avg];

			if (mcard < mid) {
				rIndex = avg-1;
			} else if (mcard >= mid) {
				lIndex = avg+1;
			}
		}

		return lIndex;

	}

}