[문제 링크](https://www.acmicpc.net/problem/10816)
💡 이분 탐색/자료 구조/해시를 사용한 집합과 맵/정렬
Memory: 8180KB Time: 644ms Code Length: 969B
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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> dict;
vector<int> target;
int N, M;
void init() {
cin >> N;
for (int i = 0; i < N; i++) {
int num;
cin >> num;
dict.push_back(num);
}
cin >> M;
for (int i = 0; i < M; i++) {
int num;
cin >> num;
target.push_back(num);
}
sort(dict.begin(), dict.end());
}
int upper_bound(int find_val) {
int st = 0;
int en = N;
while (st < en) {
int mid = (st + en) / 2;
if (dict[mid] > find_val) {
en = mid;
}
else {
st = mid + 1;
}
}
return st;
}
int lower_bound(int find_val){
int st = 0;
int en = N;
while (st < en) {
int mid = (st + en) / 2;
if (dict[mid] >= find_val) {
en = mid;
}
else {
st = mid + 1;
}
}
return st;
}
int main() {
init();
for (auto a : target) {
// cout << upper_bound(dict.begin(), dict.end(), a) - lower_bound(dict.begin(), dict.end(), a) << " ";
cout << upper_bound(a) - lower_bound(a) << " ";
}
}
이 코드는 입력된 숫자들을 정렬한 후에 이분 탐색을 사용하여 upper_bound와 lower_bound를 구하는 기능을 제공한다. init 함수에서는 입력된 숫자들을 dict와 target 벡터에 저장하고, dict를 정렬한다. upper_bound 함수는 이분 탐색을 사용하여 주어진 값보다 큰 값이 처음으로 나타나는 위치를 반환하고, lower_bound 함수는 주어진 값 이상인 값이 처음으로 나타나는 위치를 반환한다. main 함수에서는 target 벡터에 있는 각 값을 대상으로 upper_bound와 lower_bound를 호출하여 그 차이를 출력한다.
Memory 45800KB Time 988ms Code Length 475B
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
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
int N, M;
unordered_map<int,int> dict;
vector<int> vc;
int st = -1e9;
int en = 1e9;
void init() {
cin >> N;
for (int i = 0; i < N; i++) {
int num;
cin >> num;
if(dict[num]) dict[num] += 1;
else dict[num] = 1;
}
cin >> M;
for (int i = 0; i < M; i++) {
int num;
cin >> num;
vc.push_back(num);
}
}
int main() {
init();
for (auto num : vc) {
cout << dict[num] << " ";
}
}
이 코드는 unordered_map과 vector를 사용하여 숫자의 빈도수를 저장하고, 입력된 숫자들의 빈도수를 출력하는 프로그램이다. init 함수에서는 N개의 숫자를 입력받아 unordered_map에 각 숫자의 빈도수를 저장하고, M개의 숫자를 vector에 저장한다. main 함수에서는 vector에 저장된 숫자들을 순회하면서 해당 숫자의 빈도수를 unordered_map에서 찾아 출력한다.
