[BAE/<JOON> 문제풀이] 10989. 수 정렬하기3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

오늘 일어나서 너무 기운이 없어서 쉬운 문제 풀고 좀 쉴라했는데...

 

그럴라고 쉬워보이는 문제 집었는데.. 어이없게 계속 못풀었다.

 

문제를 보면 주어지는 숫자의 범위를 10000까지의 자연수로 한정하고 있다.

 

즉, 10000까지의 숫자가 각각 몇번씩 나오는지만 세서 순차 출력하면 되는 문제다.

 

그런데 자꾸 시간 초과가 뜨는 것이다...

 

거진 4시간 가량을 고민하며 혹시 분할정복문제인가 하며 퀵정렬 분할 임계점이나 검색하고 있었다.

 

그러다 결국 찾은 답은 입출력에서의 속도 차이였다. ㅡㅡ

 

//틀린 코드

#include <iostream>

using namespace std;

int arr[10001] = { 0, };
int n;

int main()
{        
    cin >> n;        
    int mx = -9999;   
    for (int i = 1; i <= n; i++) {
         int imsi;
         cin >> imsi;
        arr[imsi]++;
        if (imsi > mx) mx = imsi;
    }


    for (int i = 1; i <= mx; i++) {
        for (int j = 1; j <= arr[i]; j++) {
            cout << i << endl;
        }
    }
    
    return 0;
}

 

예제에서의 입력이 최대 1000만개다.

 

우선 기본적으로 cin과 cout은 scanf, printf 보다 느리다. 그리고 endl은 개행 문자의 출력 뿐 아니라 스트림의 버퍼를 flush하는 기능이 있기 때문에 단순 \n출력보다 느리다. 

 

//맞은 코드
#include <iostream>

using namespace std;

int arr[10001] = { 0, };
int n;

int main()
{    
    ios_base::sync_with_stdio(false); //c스트림과 동기화하지 않음
    cin.tie(NULL);
    cin >> n;        
    int mx = -9999;
    int imsi;
    for (int i = 1; i <= n; i++) {
        cin >> imsi;
        arr[imsi]++;
        if (imsi > mx) mx = imsi;
    }


    for (int i = 1; i <= mx; i++) {
        for (int j = 1; j <= arr[i]; j++) {
            cout << i << "\n";
        }
    }
    
    return 0;
}

 

ios_base::sync_with_stdio(false) : 표준 입출력 스트림을 원래 c 스트림을 사용하지만 해당 코드를 사용하면 c++의 독자적인 스트림을 이용하게됨. 결과적으로 스트림을 사용하는 스레드가 줄어드므로 속도가 향상됨

 

cin.tie(NULL) : cout과의 tie를 해제함. cin과 cout은 서로 tie되어있는 상태이기 때문에 굳이 flush를 하지 않아도 반대편 스트림에 입출력이 들어오면 버퍼에 있는 내용을 flush한다.

 

 

위 두줄의 코드는 한마디로 스트림에 걸어진 제한을 살짝 풀어주어 속도를 높이는 방식이다. 

 

근데 저럴빠에 입출력 양이 크다면 그냥 scanf, printf쓰는게 나을거 같다.