###요약 : 표준 입출력 방식의 속도 차이가 큰가요?
acmicpc.net에서 이 문제를 풀다가 시간초과로 많이 틀렸네요. (쉬운 문제라 생각하고 가볍게 풀려고 했는데 계속 시간 초과가 떠서 당황했네요;;)

먼저 이 코드는 STL을 사용해서 간단하게 문제를 풀려고 했는데 시간 초과가 떴습니다;;
~~~ c++
#include
#include
#include
using namespace std;

int main() {
// 일단 수들을 numbers에 담아 정렬한다.
vector numbers;
int n;
cin >> n;
numbers.reserve(n);
for (int i = 0; i < n; i++) {
int value;
cin >> value;
numbers.push_back(value);
}
sort(numbers.begin(), numbers.end()); // sort()는 퀵정렬 기반
// 이 후 주어진 수들을 이진 탐색으로 찾는다.
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int value;
cin >> value;
cout << binary_search(numbers.begin(), numbers.end(), value) << endl; // 이진 탐색
}
}
~~~

위 코드가 시간초과가 떠서 그럴리는 없겠지만 혹시 sort()가 퀵정렬시 pivot값 설정을 평범하게 해서 정렬시 최대 O(N^2)이 나오나 싶었습니다. 그래서 qsort() 함수를 사용해서 풀어보고자 다음과 같이 코드를 냈습니다.
~~~ c++
#include
#include
using namespace std;

int compareInt(const void* a, const void* b) {
if ((int)a < (int)b) return -1;
else if ((int)a == (int)b) return 0;
else return 1;
}

int main() {
// 일단 수들을 담을 배열을 동적할당한 후 넣고 정렬한다.
int* numbers;
int n;
cin >> n;
numbers = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
cin >> numbers[i];
}
qsort(numbers, n, sizeof(int), compareInt);
// 이진 탐색으로 찾는다.
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int value;
cin >> value;
if (bsearch(&value, numbers, n, sizeof(int), compareInt) != NULL)
cout << 1 << endl;
else
cout << 0 << endl;
}
}
~~~
위 코드 역시 시간초과가 떴습니다;; 이유를 알 수 없다가 혹시나 하는 마음에 입출력 방식을 바꿨습니다. (배열도 그냥 잡아놓고)
~~~ c++
#include
#include

int Numbers[100000];

int compareInt(const void* a, const void* b) {
if ((int)a < (int)b) return -1;
if ((int)a == (int)b) return 0;
if ((int)a > (int)b) return 1;
}

int main() {
int n;
scanf("%d", &n);
for (int i = 0; i<n; i++)
scanf("%d", Numbers + i);
qsort(Numbers, n, sizeof(int), compareInt);
int m;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int value;
scanf("%d", &value);
if (bsearch(&value, Numbers, n, sizeof(int), compareInt) != NULL)
printf("1\n");
else
printf("0\n");
}
}
~~~
시간 제한 2초를 못 넘었던 게 88ms 뜨더니 가볍게 성공했습니다. -_-;;
제가 입출력 방식으로 시간 초과가 뜬 적이 없던 터라 이게 이렇게 큰 차이인 줄 몰랐는데 이게 그렇게 차이가 큰가요?