[백준 / C++] 10989번: 수 정렬하기 3 풀이

문제 설명

 

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

10989번: 수 정렬하기 3

 

문제

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

 

입력

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

 

출력

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

 

 

 

 

 

문제 풀이

 

시간제한이 8초이고 메모리 제한이 8MB인데, 최대 N의 값이 10,000,000이기 때문에 보통의 정렬로는 해결할 수 없습니다. 

 

이 경우 정렬해야 하는 수의 범위가 1 이상 10,000 이하이므로 크기가 10,000인 배열을 만들어서 해당 숫자의 개수를 세는 방식으로 문제를 풀어야 합니다. 

 

예를 들어 입력으로 2, 2, 3, 1, 5, 3이 들어왔을 경우를 생각해봅시다. '1'이 1개, '2'가 2개, 3이 '2'개, '4'가 0개, '5'가 1개입니다. 숫자의 개수를 크기가 6인 배열에 담는다면 다음과 같을 것입니다. 

 

0	1	2	3	4	5
0	1	2	2	0	1

이때 주의할 점은 배열의 index는 0부터 시작하므로 배열의 크기가 최댓값보다 1 커야 합니다. 

숫자의 개수를 저장한 배열을 완성했다면, 해당 숫자를 개수만큼 출력해주면 됩니다. 

 

 

 

이 문제의 경우 cin, cout, endl을 그냥 사용하면 시간 초과가 뜹니다. 

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

위 코드를 입력해서 cin, cout 속도를 높여주고 endl 대신 '\n'를 사용해야 합니다. 

 

 

 

 

소스코드

 

// 10989번: 수 정렬하기 3
#include <iostream>
 
using namespace std;
 
int n;
int cnt[10001]; // 숫자의 개수를 저장하는 배열
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int num;
    cin >> n;
    // 숫자의 개수 세기
    for (int i = 0; i < n; i++) {
        cin >> num;
        cnt[num]++;
    }
 
    // 숫자의 개수만큼 출력
    for (int i = 1; i < 10001; i++) {
        while (cnt[i] != 0) {
            cout << i << '\n';
            cnt[i]--;
        }
    }
}

 

 

 

 

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)