[백준] 10989번 : 수 정렬하기 3 | C++

1. 문제 상세

 

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

 

 

 

2. 문제 접근

 

이번 문제에서는 조건으로 수의 갯수와 수가 자연수이고 수의 최대값이 주어졌다.

최대값이 10000인데, 이런 경우 원소들을 비교하며 정렬하는 방식이 아닌

카운팅 정렬(계수 정렬)로 더욱 빠르게 정렬해 볼 수 있다.

 

계수 정렬 알고리즘에 대해 정리한 글

https://dry-programming.tistory.com/111

계수 정렬 (Counting sort)

 

위의 글을 통해 계수 정렬 알고리즘을 구현하고 문제에 활용하자.

다만 이번 문제의 제한 시간과 메모리 제한을 생각하여 코드를 사용하자.

 

시간 제한을 해결하기 위해

https://dry-programming.tistory.com/31

[백준] 15552번 : 빠른 A+B | C++

 

위의 문제에서 활용한 

cin,tie(NULL) 과 ios_base::sync_with_stdio(false); 를 활용하여

입출력 딜레이를 줄이고 실행 시간을 단축하자.

 

 

 

3. 문제 풀이

 

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, a, count[10001] = { 0, };

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a;
        count[a]++;
    }

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

 

입출력의 묶음을 풀고 iostream 과 stdio 의 동기화를 줄여 실행 시간을 단축시킨다.

 

정수형 변수 n, a 와 크기가 10001인 배열 count 를 선언하고 배열의 값을 모두 0으로 초기화한다.

// 0~10000 의 숫자 개수를 카운트할 배열을 선언한다.

 

cin 으로 정수(정수의 개수)를 입력받아 n 에 저장한다.

 

for문으로 i 가 0부터 n 보다 작을 때 1씩 더하며 반복, 반복에서는 cin으로

정수를 입력받아 a 에 저장하고, count 의 a 번 인덱스의 값을 1 증가시킨다.

/* for문으로 n 번 반복하며 수를 입력받고, 카운터 배열에서 입력받은 수를 인덱스로

그 값을 증가시켜 입력받은 값의 카운트를 증가시킨다. */

 

for문으로 i 가 1부터 10001 보다 작을 때 1씩 더하며 반복한다.

// 1부터 10000까지의 수의 갯수를 확인하는 반복 실행.

반복에서는 다시 for문으로 j 가 0부터 count 의 i 번 인덱스의 값보다 작을 때 1씩 더하며 반복.

cout 으로 i 와 개행문자를 출력한다.

// 수의 개수만큼 출력하도록 한다.

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

계수 정렬을 사용해 보았다.

 

문제를 해결하다가 궁금한 점이 생겼는데,

문제에서 정렬 해야 할 수는 10000까지의 '자연수'라고 하였다.

 

여기서 자연수라면 0이 포함되는것인가? 라는 의문이 들었는데

문제를 제출해보니 0을 포함시키지 않아도 결과가 정답으로 나왔다.

 

좀 더 찾다 보니 아래의 글을 찾게 되어 대부분의 백준 문제는

'자연수' 라는 조건에서 0을 포함하지 않는다는 것을 알게 되었다..

https://www.acmicpc.net/board/view/52247

글 읽기 - 자연수는 0을 포함하나요?