- 선형탐색을 진행할 경우 O(N*M) 이므로 약 10,000,000,000 는 시간초과에 걸릴 것 같습니다.
- O(NlogN) 정렬 + O(M*logN) 이분탐색 으로 해결했습니다.
2. 주의사항
- 조건으로 인한 시간초과
3. 나의코드
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int Narr[100000];
int N, M;
bool existnum(int target) {
int ep = N - 1;
int sp = 0;
int mid;
while (sp<=ep) {
mid = (sp + ep) / 2;
if (Narr[mid] == target) { return true; }
else if (Narr[mid] < target) {
sp = mid + 1;
}
else if (Narr[mid] > target) {
ep = mid - 1;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> Narr[i];
}
sort(Narr, Narr+N); //이분탐색을 위한 정렬
cin >> M;
int target;
for (int i = 0; i < M; i++) {
cin >> target;
cout << existnum(target)<<"\n";
}
return 0;
}
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int N, M;
vector<long long> arr;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N >> M;
long long tt;
for (int i = 0; i < N; i++) {
cin >> tt;
arr.push_back(tt);
}
int tmpsum = arr[0];
int resultcount = 0;
int sp = 0;
int ep = 0;
while (1) {
if (tmpsum == M) {
resultcount++;
tmpsum -= arr[sp];
sp++;
ep++;
if (ep == N) break;
tmpsum += arr[ep];
}
else if (tmpsum < M) {
ep++;
if (ep == N) break;
tmpsum += arr[ep];
}
else if (tmpsum > M) {
tmpsum -= arr[sp];
sp++;
}
}
cout << resultcount;
return 0;
}
