(C++) - 백준(BOJ) 1926번 : 수 정렬하기 5

www.acmicpc.net/problem/15688

15688번: 수 정렬하기 5

counting sort를 사용하는 문제였습니다.

 

 

풀이방법

 1. 입력받은 수를 세줍니다. x라는 수의 개수는 num이라는 배열의 x번째 index의 값이 됩니다.

 *음수 입력이 들어올 수 있으니 index를 100만만큼 더한 후 해당 index 값을 1씩 증가하도록 합니다.

 

이런식으로 입력이 들어왔다고 가정했을 때 배열의 index로는 음수를 표현할 수 없으므로 오른쪽으로 100만칸을 미는겁니다.

 

2. 출력합니다. num[i]가 0일 때까지 i-1000000을 출력해줍니다. 

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n;
int num[200'0001];
int main(){
    fastio;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        num[x + 1000000]++;
    }
    for(int i = 0; i <= 2000000; i++){
        if(!num[i]) continue;
        while(num[i]--) cout << i - 1000000 << '\n';
    }
}