[C++] 백준 1920 : 수 찾기
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int A[100001] = {0};
void search(int n, int key){ //이진탐색(Binary Search) - 중위순회
int start = 0;
int end = n-1;
int mid;
while(end - start >= 0){
mid = (start + end)/2; // 중앙값
if(A[mid] == key){ //key 값 = 중앙값
printf("1\n");
return ;
}else if(A[mid] > key) { //key 값 < 중앙값
end = mid - 1;
}else{ //key 값 > 중앙값
start = mid + 1;
}
}
printf("0\n");
return ;
}
int main(int argc, char **argv){
int x;
scanf("%d",&N);
for(int i=0; i<N; i++){
scanf("%d",&A[i]);
}
sort(A, A + N); // 정렬
scanf("%d",&M);
for(int i=0; i<M; i++){
scanf("%d", &x);
search(N, x);
}
return 0;
}
오늘의 키포인트
- 시간 초과 에러
- 정렬시킨 후 이진탐색(중위순회)를 이용해서 탐색 시간을 줄였다.
std::binary_search 를 사용해 볼 수도 있을 것 같다.
Author And Source
이 문제에 관하여([C++] 백준 1920 : 수 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-1920-수-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)