[백준 알고리즘/ C++] BOJ.10989 : 수 정렬하기 3

 

문제

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

10989번: 수 정렬하기 3

 

 

---

풀이

자료구조

- int num : 입력 수
- int temp : 입력받은 수
- int count_sort[] : 카운트 할 배열

 

알고리즘

- 입력 개수가 천만개가 들어오면 메모리 제한을 넘어버려서 일반적인 정렬 알고리즘은 쓸 수 없었음

- 수가 10,000으로 제한되어 있기 때문에 이 경우 카운트 정렬을 통해 풀어도 되겠다고 생각함

 

코드

- C++에서 표준입출력으로 쓰는 cin이랑 cout는 실행시간이 느려서 계속 시간초과가 뜬다.

- C에서 쓰는 scanf랑 printf로 변경

---

코드 

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

int main() {
    int num = 0;
    int temp = 0;
    int count_sort[100001] = {0};

    cin >> num;
    for (int i = 0; i < num; i++) {
        scanf("%d", &temp);
        count_sort[temp]++;
    }

    for (int i = 1; i <= 10001; i++) {
        for (int j = 0; j < count_sort[i]; j++) {
            printf("%d\n", i);
        }
    }
    return 0;
}

 

---

총평

 

cin, cout 때문에 시간초과 엄청 났다...

찾아보니 cin이랑 scanf는 속도가 두배 이상 차이가 난다고 한다.

알고리즘 풀 떄는 속 편하게 scanf를 쓰는 것이 좋을 거 같다.