링크 : https://www.acmicpc.net/problem/1920
N까지의 배열이 주어져 있다. X라는 정수가 존재하는지 찾아야 한다.
애초에 배열에 넣을 때 이분트리로 넣고 탐색하면 딱 좋을 것 같다.
#include<iostream>
using namespace std;
int arr[100001]{ 0, };
bool full[100001]{ false, };
int main() {
int N, elem, tmp;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> elem;
tmp = 0;
while (full[tmp] == true){
if (arr[tmp] < elem)
tmp = (2 * tmp) + 2;
else
tmp = (2 * tmp) + 1;
}
arr[tmp] = elem;
full[tmp] = true;
}
cin >> N;
for (int j = 0; j < N; j++) {
cin >> elem;
tmp = 0;
while (full[tmp] == true && arr[tmp] != elem) {
if (arr[tmp] < elem)
tmp = (2 * tmp) + 2;
else
tmp = (2 * tmp) + 1;
}
if (arr[tmp] == elem)
cout << 1 << "\n";
else
cout << 0 << "\n";
}
return 0;
}
간단한 struct를 만들어봅시당
->
포인터 정리 못해서 error
algorithm 라이브러리의 sort의 힘을 빌려서
#include<iostream>
#include<algorithm>
using namespace std;
int arr[100001];
int main() {
cin.tie(NULL);
int N, M, elem;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
sort(arr, arr + N);
bool check = false;
cin >> M;
for (int i = 0; i < M; i++) {
cin >> elem;
int start = 0, end = N - 1, mid;
while (start <= end){
mid = (start + end) / 2;
if (arr[mid] < elem) {
start = mid+1;
}
else if(arr[mid] > elem){
end = mid-1;
}
else {
check = true;
break;
}
}
if (check) {
cout << "1\n";
check = false;
}
else
cout << "0\n";
}
return 0;
}
아 쉬운건데 왜 시작할 때 1번째 out of bounds를 놓쳤는지 모르겠다. 마지막으로 while (start <= end)
이 조건을 세울 때 mid는 설정하지 않아도 start<=end
만 세워준다면 문제 없을 것이라는 것도 잊어버렸다.
그리고 한번 체크된 거 다시 초기화해주는 것. 또 까먹었다.
if (check) {
cout << "1\n";
check = false;
}