[PS] 문제풀이/백준
[ 백준 1920 ] 수 찾기 (C++)
안산학생
2020. 2. 3. 22:57
[해결과정]
1. 수 입력 받기.
2. 오름차순 정렬 (sort)
3. 문제 입력 받기 ( 입력 받고 바로 결과 값 도출)
4. 이분 탐색 활용
5. 이분 탐색은 값을 기준이 아닌 배열의 idx 값을 기준으로 이분 탐색 시행
[소스코드]
|
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
|
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<memory.h>
#include<cstring>
using namespace std;
int arr[100001];
int n,m;
bool ans;
void search(int s, int e, int find) {
if (ans == true) return;
if (s > e) return;
int mid = (s + e) / 2;
if (arr[mid] == find) {
ans = true;
return;
}
if (arr[mid] >= find) {
e = mid;
search(s, mid-1, find);
}
else {
s = mid;
search(mid+1, e, find);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr, arr + n);
cin >> m;
for (int i = 0; i < m; i++) {
ans = false;
int temp;
cin >> temp;
search(0, n - 1, temp);
if (ans == 1) cout << 1 << "\n";
else cout << 0 << "\n";
}
return 0;
}
|
[해결 과정 중 실수한 부분]
이분 탐색은 사실 겁 먹어서 구현을 피해왔던 문제였는데, 오늘 공부하며 완벽하게 숙지했다. 실수 한 부분은 s와 e에 mid값을 계속 저장했는데, 그럴 필요없이 매개 변수에 mid+1, mid-1 식으로 하면 간단했다는 거 정도!
[관련 문제 혹은 비슷한 문제]
이분 탐색