[백준/Java] 10816 숫자카드 2

조건

1. 숫자 카드의 개수는 N개(1<= N <=500,000)이다.

2. 숫자의 값으 -천만에서 천만까지이다.

3. 숫자를 비교할 정수의 개수가 입력되고 공백으로 구분되어있다.

예제 입력

해결

저번에 풀었던 숫자카드와 같지만 차이는 count를 해야한다는 것이다.
그렇기에 해당 숫자가 몇개가 있어야하는가를 알아야하고 원하는 숫자가 없다면 0으로 출력해야 하는 상황이다. 일일이 비교하기에는 시간초과가 발생하니 N개의 정수를 입력받고 난 후 정렬을 하고 숫자를 이분탐색으로 배열의 인덱스 위치를 탐색한다. 이 때 2가지를 찾을 것인데 하나는 비교하는 숫자가 시작하는 인덱스와 다른 하나는 비교하는 숫자 바로 다음 숫자의 인덱스를 찾을 것이다. 이렇게 하는 이유는 숫자가 여러개가 나온다면 while을 통해 +1씩 더하며 인덱스의 카운트를 세는 것 보다 더 빠르고 쉽기 때문이다

다음과 같이 3을 비교할 정수라면 앞에서 말한 것처럼 비교할 숫자 다음의 인덱스 value가 4인 5를 찾아오고 비교할 숫자의 시작 인덱스를 2를 가지고 온다 그 후
다음 인덱스 - 시작 인덱스를 해주면 = 정수 3의 개수는 3이 나오는 것을 알 수 있다.

코드

import java.io.*;
import java.util.*;



public class Main {
	
	static int N, M;
	static int[] A,B;
	
	
	static FastReader scan = new FastReader();
	static StringBuilder sb = new StringBuilder();

	static void input() {
		
		N = scan.nextInt(); // 정수의 개수를 받고
		A = new int[N + 1]; // index의 시작을 1로 하기위해 +1
		
		for(int i=1;i<=N;i++) {
			A[i] = scan.nextInt(); // 정수 값 받기
		}
		

		
	}
	static int low_findAns(int[] A, int L, int R, int X) {
		int ans = R + 1;
		while(L<=R) {
			int mid = (L + R) / 2;
			if(A[mid] >= X) { // 시작하는 값을 찾기 위해 비교하는 값의 이상을 								 // 찾기
				ans = mid;
				R = mid - 1;
			}else {
				L = mid + 1;
			}
	}
		return ans;
		
	}
	
	
	static int high_findAns(int[] A, int L, int R, int X) {
		int ans = R + 1;
		
		while(L<=R) {
			int mid = (L + R) / 2;
			if(A[mid] > X) { // 비교할 인덱스 바로 위의 값을 찾기 위해 초과							  // 값을 찾기
				ans = mid;
				R = mid - 1;
			}
			else {
				L = mid + 1;
		}
			
		}
		return ans;
	}
	

	
	
	
	static void find() {
		Arrays.sort(A,1,N+1); // 오름차순으로 배열 정렬
		M = scan.nextInt(); // 비교할 정수 개수 받기
		for(int j = 1;j<=M;j++) {
		int X = scan.nextInt(); // 비교할 정수 값
		int low = low_findAns(A,1,N,X); // 인덱스 시작 값 찾기
		int high = high_findAns(A,1,N,X); // 인덱스 다음 정수 인덱스 값
		sb.append(high - low).append(' '); // 빼기 해서 카운트 입력
			}
			
		System.out.println(sb);
		}

		
		
	

	public static void main(String[] args) {
		input();
		find();
	}
	// 데이터 입력을 받기 위한 함수 선언
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}
		
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		Long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			}catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}