[백준] 이분 탐색 - 10816번 숫자카드2 java

문제 

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

10816번: 숫자 카드 2

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

풀이

이전 문제와 달리 이 문제는 중복되는 값의 개수를 구해야한다.

구하는 방법은,

상한(찾고자하는 값을 초과하는 값이 처음으로 나타나는 위치) - 하한(찾고자하는 값 이상의 값이 처음으로 나타나는 위치)를 구하면 된다.

 

코드

package 이분탐색;
import java.util.*;
public class No10816_숫자카드2 {

	static int[] A;
	static int[] B;
	public static void main(String[] args) {
		 
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		
		Arrays.sort(arr);	// 이분 탐색을 하기 위해서는 반드시 정렬되어있어야 한다.
		
		int M = sc.nextInt();
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < M; i++) {
			int key = sc.nextInt();
			
			//중복 원소에 대한 길이 = 상한 - 하한 
			sb.append(upperBound(arr, key) - lowerBound(arr, key)).append(' ');
		}
		System.out.println(sb);
	}
 
	
	//찾고자 하는 값 이상의 값이 처음으로 나타나는 위치 
	private static int lowerBound(int[] arr, int key) {
		int left=0;
		int right=arr.length;
		
		while(left<right) {
			int mid=(left+right)/2;
			
			if(key<=arr[mid]) {
				right=mid;
			}
			else {
				left=mid+1;
			}
		}
		
		return left;
	}
	
	//찾고자 하는 값 초과의 값이 처음으로 나타나는 위치 
	private static int upperBound(int[] arr, int key) {
		int left=0;
		int right=arr.length;
		
		while(left<right) {
			int mid=(left+right)/2;
			
			if(key<arr[mid]) {
				right=mid;
			}
			else {
				left=mid+1;
			}
		}
		
		return left;
	}
}