💡 이분 탐색/자료 구조/해시를 사용한 집합과 맵/정렬
Memory 2800KB Time 48ms Code Length 740B
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
#include <iostream>
#include <algorithm>
using namespace std;
int dict_arr[100000];
int find_arr[100000];
int N, M;
void init() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> dict_arr[i];
}
cin >> M;
for (int i = 0; i < M; i++) {
cin >> find_arr[i];
}
sort(dict_arr, dict_arr + N);
}
int solved(int find_val) {
int st = 0;
int en = N - 1;
while (st<=en) {
int mid = (st + en) / 2;
if (dict_arr[mid] < find_val) {
st = mid+1;
}
else if (dict_arr[mid] > find_val) {
en = mid-1;
}
else {
return 1;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
init();
for (int i = 0; i < M; i++) {
int result = solved(find_arr[i]);
cout << result << "\n";
}
}
이 코드는 이진 탐색 알고리즘을 사용하여 주어진 정렬된 배열에서 원하는 값을 찾는 프로그램이다.
init() 함수에서는 입력값을 받고, dict_arr 배열을 정렬한다.
solved() 함수는 이진 탐색을 수행하여 find_val 값을 찾는다.
main() 함수에서는 init() 함수를 호출하고, find_arr 배열의 각 요소에 대해 solved() 함수를 호출하여 결과를 출력한다.
위와 같이 풀었을 때 쉽게 구현 가능하지만, 메모리와 시간이 매우 많이 든다. 즉, 리소스를 많이 잡아먹는다.
그렇기에 좀 더 최적화된 이분 탐색을 이용해보았다.
STL의 upper_bound, lower_bound를 사용하여 찾는 값의 바운더리 값을 바로 찾아서 계산 할 수 있고, 이전에 풀었던 1920-수 찾기 문제의 binary_search 함수를 응용하여 쉽게 풀 수 도있다.
두 함수의 차이는 target과 dict[mid] 값이 같을 때의 경우를 어느 조건문에 같이 넣어 주느냐에 따라 upper_bound 값과 lower_bound 값이 바뀌게 된다. 그리고 while문 조건에 st와 en이 같아진 경우에 더 이상의 변화는 필요 없다. 고로 st와 en이 다를 때 까지만 돌려주면 된다.
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) << " ";
}
}
결과.
(아래 : unordered_map, 위 : 이분 탐색)
