숫자 개수 세기

문제

n개의 숫자가 주어지고, q개의 질문이 주어진다. 각각의 질문은 n개의 숫자 중에서 특정 숫자가 몇개나 있는지를 묻는다. q개의 질문에 모두 답하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 주어지는 q개의 질문에 해당하는 숫자 범위는 100,000,000이하이다.  

출력

각 질문에 대하여 숫자의 개수를 한 줄에 하나씩 출력한다.  

예제 입력

10 4
1 3 4 3 2 3 1 2 5 10
1 3 9 10

예제 출력

2
3
0
1

 

// 코드

import java.util.*;
import java.util.Map.*;
import java.io.*;
 
public class Main{
  
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static int n, q;
  static int[] arr;
  static Map<Integer, Integer> map = new HashMap<>();
  
  static boolean binarySearch(int start, int end, int value) {
    
    if(start>end) return false; // 기저조건
    else if (start == end){ // 기저조건
      if(arr[start] == value) return true;
      else return false;
    } else {
      
      int mid = (start + end) / 2;
      if(arr[mid] == value) return true;
      else if(arr[mid] > value) return binarySearch(start, mid-1, value);
      else return binarySearch(mid+1, end, value);
      
    }
    
  }
  
  public static void main(String[] args) throws Exception {
    
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    n = Integer.parseInt(st.nextToken());
    q = Integer.parseInt(st.nextToken());
    
    st = new StringTokenizer(br.readLine());
    for(int i=0; i<n; i++) {
      int num = Integer.parseInt(st.nextToken());
      if(map.get(num) == null) {
        map.put(num, 1);
      } else {
        map.put(num, map.get(num)+1);
      }
    }
    
    arr = new int[map.size()];
    int idx = 0;
    for(Entry<Integer, Integer> entrySet : map.entrySet()) {
      arr[idx++] = entrySet.getKey();
    }
    
    Arrays.sort(arr);
    StringBuilder sb = new StringBuilder();
    st = new StringTokenizer(br.readLine());
    for(int i=0; i<q; i++) {
      int value = Integer.parseInt(st.nextToken());
      boolean resFlag = binarySearch(0, arr.length-1, value);
      if(resFlag) {
        sb.append(map.get(value) + "\n");
      } else {
        sb.append("0\n");
      }
    }
    
    bw.write(sb.toString());
    br.close();
    bw.flush();
    bw.close();
  }
}