- 문제 (1920번) : 수 찾기
- N개의 정수가 주어져 있을 때 이 안에 X라는 정수가 존재하는지 알아내는 프로그램 구현.
- 입력 및 출력
[ 입력]
- 첫번째 줄에 정수의 개수 N 입력 ( 1 ≤ N ≤ 100,000 , 자연수 )
- 두번째 줄에 N개의 정수 입력
- 세번째 줄에 정수의 개수 M 입력
- 네번째 줄에 M개의 정수 입력
- ( 1 ≤ N ≤ 100,000 , 자연수 )
- ( -2³¹ ≤ N, M을 제외한 모든 정수 ＜ 2³¹ )
[ 출력]
- M개의 줄에 답을 출력
- N개의 정수에 네번째 줄에 입력받은 정수가 있으면 1, 없으면 0을 출력
- 문제 풀이
- 이번 수 찾기 문제는 탐색문제이다. 그래서 이번에 이진탐색으로 구현해봤다.
- c++ 에는 'algorithm' 헤더에 binary_search 함수가 내장되어있으므로 이 함수를 사용해 문제를 해결했다.
- N개의 정수를 입력받아 vector에 저장한 후 sorting을 해준다.
- 그 후 M개의 정수를 입력받고 binary_search 함수를 사용해 출력한다.
- 이번 수 찾기문제는 알고리즘자체는 생각하기 쉬웠다.
하지만 시간초과가 계속해서 발생했다.
이것을 해결하고자 구글링을 해봤고, "std::cout << std::endl" 보다 printf() 가 더 빠르다는 것을 알고 출력을 printf() 로 했더니 문제를 해결하게 되었다.
- 최종 코드
