(C++) 백준 15688번 - 수 정렬하기 5

문제 링크 : https://www.acmicpc.net/problem/15688

15688번: 수 정렬하기 5

문제 풀이

계수 정렬(Counting Sort)을 이용한 풀이이다.

등장 횟수를 배열에 저장하고, 등장 횟수만큼 해당 숫자를 출력하는 형식으로 풀이했다.

#include <iostream>

using namespace std;

int a[2000002]; // 해당 숫자(-1000000~1000000)이 몇 번 나타나는지 저장하는 배열
int n, tmp;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> tmp;
        a[tmp+1000000]++; // -1000000을 index 0에 저장하기 위함
    }
    for(int i = 0; i < 2000002; i++){
        if(a[i] != 0){ // 해당 수가 등장했다면
            for(int j = 0; j < a[i]; j++){ // 등장 횟수만큼 출력
                cout << i-1000000 << "\n"; // index에 1000000을 더해줬으므로 다시 빼줌
            }
        }
    }
}