백준 문제풀이
[beakjoon-1920-C++] 수 찾기
박여치
2023. 1. 26. 11:09
문제
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
오답 코드

시간 초과로 틀린 코드입니다.
벡터에 입력값을 저장한 후, 입력값이 들어올 때마다 같은 값이 있는 지 확인하여 결과를 B 벡터에 저장합니다.
find 과정에서 처음부터 끝까지 순회하다보니 시간이 초과하여 오답 처리되었습니다.
※시간복잡도 O(N*M)
코드

이분 탐색을 통해 같은 숫자가 있는 지, 찾는 시간을 줄인 코드입니다.
이분 탐색을 위해 sort함수를 통해 오름차순 정렬하였습니다.
※시간복잡도 O(M*logN)