[정렬] 백준 10989 :: 수 정렬하기 3

수 정렬하기 3 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초 (하단 참고)	8 MB (하단 참고)	38248	7943	5904	23.294%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1 

1
1
2
2
3
3
4
5
5
7

 

 문제풀이

1차 문제풀이 (1988 KB,  1648 ms)

데이터의 수는 많지만,  

도메인이 좁으므로 카운트 솔팅이 효과적이다.

콘솔 입출력에서 병목이 발생됨이 예상되므로,

stdio와의 동기화를 풀어야 한다.

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


int main() {
        //! 빠른 입출력을 위해...
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);


        int N = 0, val;
        int cnt[10001];
        memset(cnt, 0, sizeof(cnt));

        cin >> N;
        for(int i=0; i<N; i++){
                cin >> val;
                cnt[val]++;
        }
        for(int i=0; i<=10000; i++){
                for(int j=0; j<cnt[i]; j++){
                        cout << i << '\n';
                }
        }
}

2차 문제풀이 (4036 KB,  372 ms)

fread,  fwrite + 버퍼링.

#include <iostream>
#include <cstring>
using namespace std;

const int BUF_SIZE = 1 << 20;
char input_buf[BUF_SIZE], output_buf[BUF_SIZE];
int input_buf_pos, output_buf_pos;
enum io_mode {READ, WRITE};


inline void char_io(io_mode mode, char &target)
{
        if(mode == READ) {
                if (input_buf_pos == BUF_SIZE)
                {
                        fread(input_buf, sizeof(char), BUF_SIZE, stdin);
                        input_buf_pos = 0;
                }
                target = input_buf[input_buf_pos++];
        }
        else {
                if(output_buf_pos == BUF_SIZE || target == EOF)
                {
                        fwrite(output_buf, sizeof(char), output_buf_pos, stdout);
                        output_buf_pos = 0;
                }
                output_buf[output_buf_pos++] = target;
        }
}
inline void char_io(io_mode mode, char &&target){
        char_io(mode, target);
}


inline void int_io(io_mode mode, int &target)
{
        char c;
        if(mode == READ){
                bool negative = false;
                int ret = 0;
                while(true)
                {
                        char_io(READ, c);
                        if(c == '\n' || c == ' ') break;
                        if(c == '-') {
                                negative = true;
                                continue;
                        }
                        ret = ret * 10 + (c & 0b1111);
                }
                target = negative ? -ret : ret;
        }
        else {
                int abs = target;
                int div = 1'000'000'000;
                char quotient = 0;
                if(abs < 0) {
                        char_io(WRITE, '-');
                        abs *= -1;
                }
                while(abs < div && div != 1) { div /= 10; }
                while(div != 0){
                        quotient = '0' + (char)((abs / div)%10);
                        char_io(WRITE, quotient);
                        div /= 10;
                }
        }
}
inline void int_io(io_mode mode, int &&target){
        int_io(mode, target);
}

int main() {
        int N = 0, val;
        int cnt[10001];
        char num[15];
        memset(cnt, 0, sizeof(cnt));

        int_io(READ, N);
        for(int i=0; i<N; i++){
                int_io(READ, val);
                cnt[val]++;
        }
        for(int i=0; i<=10000; i++){
                for(int j=0; j<cnt[i]; j++){
                        int_io(WRITE, i);
                        char_io(WRITE, '\n');
                }
        }
        char_io(WRITE, EOF);
}