[c++] scanf & cin 속도 차이(입력 시간 초과)

 

이분 탐색을 이용하는 간단한 문제였다.

첫번째 시도에서 이분 탐색을 사용하지 않았었고, 시간 초과가 발생하는걸 보고 이분 탐색을 도입했는데 계속해서 시간초과가 발생했다.

 

왜지..?

 

원인은 생각지도 못한 곳에 있었다.

 

두 코드의 차이점이 그 원인이다.

 

#include <bits/stdc++.h>
using namespace std;

vector<int> v;
int N, M;

int main()
{
    cin >> N;
    int input;
    for (int i = 0; i < N; i++)
    {
        cin >> input;
        v.push_back(input);
    }

    sort(v.begin(), v.end());

    cin >> M;

    for (int i = 0; i < M; i++)
    {
        cin >> input;
        if (binary_search(v.begin(), v.end(), input))
        {
            cout << "1 ";
        }
        else
        {
            cout << "0 ";
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<int> v;
int N, M;

int main()
{
    cin >> N;
    int input;
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &input);
        v.push_back(input);
    }

    sort(v.begin(), v.end());

    cin >> M;

    for (int i = 0; i < M; i++)
    {
        scanf("%d", &input);
        if (binary_search(v.begin(), v.end(), input))
        {
            cout << "1 ";
        }
        else
        {
            cout << "0 ";
        }
    }
}

 

 

 

바로 그 원인은 std::cin 이였다. scanf에 비해 비교적 쉽게 입력을 받을 수 있어서, 지금까지 거의 모든 문제를 cin을 이용하여 풀었던 것 같다. 이게 원인이였다니....

이번 기회에 scanf와 cin의 속도를 찾아보았다.

 

https://algospot.com/forum/read/2496/

 

위 사진을 보면 알겠지만, 시간 차이가 꽤 엄청나다... 10만번 이상의 입력이 이루어진다면 이는 시간초과를 일으킬만큼 강력해진다.

 

조심..조심하쟈..