-
1920번 숫자 찾기ComputerScience/코딩테스트 2019. 11. 23. 22:55
https://www.acmicpc.net/problem/1920
단순 배열 2개를 만들어서 무작정 찾으려하니 '시간초과'가 발생하였다.
이진탐색을 이용하여 탐색하였다.
시간복잡도를 O(logn)으로 줄인다.
c++의 vector을 사용했다.
cin의 시간초과를 막기 위해
ios_base::sync_with_stdio(0);
cin.tie(0);
라는 코드를 써준다.
#include <iostream> #include <algorithm> #include <vector> using namespace std; const int MAX = 100000; int N, M; vector<int> A; int binarySearch(int low, int high, int target){ if(low > high) return 0; else { int mid = (low + high) /2 ; if(A[mid]==target) return 1; else if(A[mid] > target) { return binarySearch(low,mid-1,target); } else return binarySearch(mid+1,high,target); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); //cin 속도 향상 위해 cin >> N; for(int i =0; i<N ;i++){ int num; cin >> num; A.push_back(num); } sort(A.begin(),A.end()); cin >> M; for (int i = 0; i < M; i++) { int num; cin >> num; cout << binarySearch(0, N - 1, num) << "\n"; //endl 쓰면 시간 초과 } return 0; }
'ComputerScience > 코딩테스트' 카테고리의 다른 글
[프로그래머스] 베스트앨범 (0) 2020.07.04 [프로그래머스] 여행경로 (0) 2020.07.03 [hash/map]Programmers 완주하지 못한 선수 (0) 2020.06.04 9012번 괄호 (0) 2020.01.06 11557 Yangjojang of The Year (0) 2019.11.27