BOJ - 10989 (C++)

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

10989번: 수 정렬하기 3

---

어떻게 풀어야 할까?

아마 이 문제를 처음 접할 때,
선택 정렬 알고리즘을 사용할 것 이다.

그러면 틀린다.
왜냐면 배열을 int 형으로 잡고 10,000,000 계산한다고 가정했을때,
보수적으로 잡아도 40MB의 메모리가 소요되기 때문이다.

선택 정렬로 풀면 이중 for문이 들어가게 된다. -> 시간 초과에서 걸린다.
그렇다면,
sort()함수를 이용해서 풀면 될까? -> 메모리 초과로 불가능

그래도 시간 초과가 난다면?

cout, cin을 사용해서 출력 및 입력을 했을 가능성이 크다.

그렇다면?
printf, scanf를 사용해서 출력해야한다.

cout, cin 보다 printf, scanf가 속도가 더 빠르다.

---

다른 방법을 사용한다.
10001개의 공간을 가진 int형 배열을 선언한다. (왜냐면 입력되는 수가 1<= n <= 10000 이기 때문에)

만약, 7이 2번 입력된다고 가정하면
arr[7]의 값을 2번 증가시킨다.

1000이 3번 입력된다면?
arr[1000]의 값을 3번 증가

그리고 1~10000까지 for문을 반복하면서,
해당 인덱스에 있는 값을 그 값만큼 출력해주면 된다.

예를 들어,
arr[100]에 3이 저장되어 있다면,
100을 3번 출력해주면 된다.

---

#include <iostream>
using namespace std;

int main(void)
{
    int N;
    scanf("%d", &N);

    int arr[10001] = {0};

    for(int i = 0; i < N; i++){
        int n;
        scanf("%d", &n);
        arr[n]++;
    }

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

---

문제를 풀며 얻어갈 것

printf / scanf가 속도가 훨씬 빠르다는 것.
배열을 사용해서 정렬을 할 수 있다는 것.