입출력 방식 속도 차이 (cin, scanf)가 큰가요?

  • robustFlame
    robustFlame

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

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

    #include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    // 일단 수들을 numbers에 담아 정렬한다.
    vector<int> 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() 함수를 사용해서 풀어보고자 다음과 같이 코드를 냈습니다.

    #include <iostream>
#include <cstdlib>
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;
    }
}

    위 코드 역시 시간초과가 떴습니다;; 이유를 알 수 없다가 혹시나 하는 마음에 입출력 방식을 바꿨습니다. (배열도 그냥 잡아놓고)

    #include <stdio.h>
#include <stdlib.h>

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 뜨더니 가볍게 성공했습니다. -_-;;
    제가 입출력 방식으로 시간 초과가 뜬 적이 없던 터라 이게 이렇게 큰 차이인 줄 몰랐는데 이게 그렇게 차이가 큰가요?


    8년 전
2개의 댓글이 있습니다.
  • stkai
    stkai

    혹시 .. cin을 사용한것도 global로 선언하고 해보셨나요?


    8년 전 link
  • wookayin
    wookayin
    • std::sort()는 빠릅니다. O(n^2) 걸릴 정도로 허술하지 않고, qsort보다도 효율적입니다. qsort는 가급적 쓰지 마세요ㅠ
    • 10만 이상의 데이터를 읽어들일 때 scanf와 cin의 속도차이는 꽤 납니다. 아마 I/O 때문에 시간초과가 났을것 같습니다.
    • 대회/문제풀이용 방법으로는 cin.sync_with_stdio(false); 를 해주면 (scanf와 혼용 사용은 불가능해지지만) cin의 I/O 속도가 빨라집니다.

    https://algospot.com/forum/read/2496/ 를 참고해보시면 좋겠네요.


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.