1. Problem 📃

[ 숫자 카드 2 ]

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

[ 문제 ]

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

2. Input 📇

[ 입력 ]

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다.
둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다.
숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다.
넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다.
이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

3. Output 📠

[ 출력 ]

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

4. Example 📚

[ 입출력 예시 ]

5. Solution 🔑

이 문제는 상근이의 카드 N개가 다음 보기에 있는 숫자 목록들 중에 해당 수가 몇 개가 있는지 출력하는 프로그램이다. 상근이의 카드를 sort()시켜서 찾고자 하는 값이 몇 번째 칸부터 몇 번째 칸까지 있는지 확인하고 그 값을 서로 빼주고 +1 해주면 개수가 나온다.
ex) 4, 5, 6, 6, 6, 7, 7 에서 6을 찾고자한다면
2 ~ 4번째 이므로 4-2(+1)를 하여 찾아주면 된다.


1. lowerBound라는 적은 인덱스 값을 탐색해주는 메서드를 하나 선언해주고, upperBound라는 큰 인덱스 값을 탐색해주는 메서드를 선언해준다.
이분탐색으로 정의하되 lowerBound는 값이 같을 때 high 값을 움직이고, upperBound는 값이 같을 때 low 값을 움직여준다.


2. 상근이의 카드 개수(N)을 입력 받아 카드 배열(owner)를 선언하여 카드를 모두 입력해준다.
그리고 owner를 sort()시켜 오름차순 정렬시켜준다.


3. 주어진 카드의 개수(M)을 선언하여 M의 개수만큼 카드를 하나씩 확인하며 정의한 메서드에 넣고 upperBound와 lowerBound의 차를 구해준다.
이때, 리턴 받는 upperBound의 값은 애초에 해당 위치보다 1높게 받으므로 1을 더할 필요없이 바로 빼주어 StringBuilder(sb)에 담아주고 다음 카드를 확인한다.


4. 최종 StringBuilder(sb)를 출력한다.

6. Code 💻

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[] owner;
	
	public static int lowerBound(int val) {
		int low = 0;
		int high = owner.length;
		
		while(low < high) {
			int mid = (low + high) / 2;
			
			if(owner[mid] >= val) {
				high = mid;
			}
			else {
				low = mid + 1;
			}
		}
		return low;
	}
	
	public static int upperBound(int val) {
		int low = 0;
		int high = owner.length;
		
		while(low < high) {
			int mid = (low + high) / 2;
			
			if(owner[mid] > val) {
				high = mid;
			}
			else {
				low = mid + 1;
			}
		}
		
		return low;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(st.nextToken());
		owner = new int[N];
		
		st = new StringTokenizer(br.readLine(), " ");
		
		for(int i=0; i<N; i++) {
			owner[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(owner);
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine(), " ");
		
		for(int i=0; i<M; i++) {
			int n = Integer.parseInt(st.nextToken());
			sb.append(upperBound(n) - lowerBound(n) + " ");
		}
		
		System.out.println(sb);
		
	}
}