10816 숫자 카드2

package baekjoon;

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

public class b10816 {
	
	public static int lowerBound(int arr[], int key) {
		int start = 0; int end = arr.length;
		
		while(start < end){
			int mid = (start+end)/2;
			if(key <= arr[mid]) {
				end = mid;
			} else {
				start = mid+1;
			}
		}
		return end;
	}
	
	public static int upperBound(int [] arr, int key) {
		int start = 0; int end = arr.length;
		while(start < end) {
			int mid = (start+end)/2;
			if(key < arr[mid]) {
				end = mid;
			} else {
				start = mid+1;
			}
		}
		return end;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int 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);
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			
			int key = Integer.parseInt(st.nextToken());
			sb.append(upperBound(arr,key) - lowerBound(arr,key)).append(' ');
		}
		System.out.println(sb);
		
	}

}

 

lowerBound : 데이터 내 특정 키값보다 같거나 큰 값이(키 값 이상의 값이) 처음 나오는 위치를 리턴

upperBound : 특정 키 값보다 처음으로 큰 값(키 값 초과하는 값)이 나오는 위치를 리턴

 

*중복된 값이 있는 배열을 정렬한 상태여야함. 

 

 

 

여기서 주의해야할 점

이진 탐색과 다른 점이 있다. 주어진 값보다 같거나 큰 값이 처음으로 나오는 것을 리턴해야함. 만약 위 경우에서 키 값이 7이라면 주어진 배열의 크기만큼 리턴되어야 하기 때문에 high(end) 값을 arr.length-1 이 아닌 arr.length로 설정 해주어야 한다. 

그리고 lowerBound와 upperBound에서 high와 low가 같아지는 값을 리턴하기 때문에 return start = end 똑같다.