본문 바로가기
[C++] 알고리즘 교육/9~10. 고급정렬

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

by 안산학생 2019. 4. 25.

문제


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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#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+1end);
    
    merging(arr, start, mid, mid+1end);
    
  }
}
 
int binarySearch(int arr[], int start, int endint 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+1end, 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;
}
 

 

댓글