[알고리즘 10.1.3] 이진탐색 - 숫자 개수 세기

문제

---

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include <stdio.h>
 
void merging(int arr[], int s1, int e1, int s2, int e2){
  int p = s1;
  int q = s2;
  
  int temp[1000005];
  int temp_idx=0;
  
  while(p<=e1 && q<=e2){
    if(arr[p]<=arr[q]){
      temp[temp_idx++] = arr[p];
      p++;
    }else{
      temp[temp_idx++] = arr[q];
      q++;
    }
  }
  
  if(p>e1){
    for(int i=q; i<=e2; i++){
      temp[temp_idx++] = arr[i];
    }
  }else{
    for(int i=p; i<=e1; i++){
      temp[temp_idx++] = arr[i];
    }
  }
  
  for(int i=s1; i<=e2; i++){
    arr[i] = temp[i-s1];
  }
  
}
 
void mergeSort(int arr[], int start, int end){
  if(start>=end){
    return;
  }else{
    
    int mid = (start+end)/2;
    
    mergeSort(arr, start, mid);
    mergeSort(arr, mid+1, end);
    
    merging(arr, start, mid, mid+1, end);
    
  }
}
 
int binarySearch(int arr[], int start, int end, int value){
  if(start>end){
    return 0;
  }else if(start==end){
    if(arr[start]==value){
      return start;
    }else{
      return 0;
    }
  }else{
    
    int mid = (start+end)/2;
    if(arr[mid]==value){
      return mid;
    }else if(arr[mid]>value){
      return binarySearch(arr,start,mid, value);
    }else{
      return binarySearch(arr, mid+1, end, value);
    }
  }
  
}
 
int main() {
 
  int n;
  scanf("%d",&n);
  
  int n2;
  scanf("%d",&n2);
  
  int arr[n];
  for(int i=0; i<n; i++){
    scanf("%d",&arr[i]);
  }
  
  mergeSort(arr,0,n-1);
  
  int arr2[n2];
  //위치 값 배열
  int temp[n2];
  //개수 값 배열
  int count[n2];
  int sum = 0;
  
  for(int i=0; i<n2; i++){
    scanf("%d",&arr2[i]);
 
    temp[i] = binarySearch(arr, 0, n-1, arr2[i]);
    
 
    for(int j=temp[i]+1; j<n; j++){
      if(arr[j]==arr2[i]){
        sum++;
      }else{
        break;
      }
    }
    
    for(int j=temp[i]; j>=0; j--){
      if(arr[j]==arr2[i]){
        sum++;
      }else{
        break;
      }
    }
    
    count[i] = sum;
    sum = 0;
    
  }
 
  
  // for(int i=0; i<n; i++){
  //   printf("%d ",arr[i]);
  // }
  
  // printf("\n");
  
  // for(int i=0; i<n2; i++){
  //   printf("%d ",temp[i]);
  // }
  
  // printf("\n");
  
  for(int i=0; i<n2; i++){
    printf("%d\n",count[i]);
  }
 
  return 0;
}