(10989) 수 정렬하기 3

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

단계별로 풀어보기

13단계(정렬) 5번째

 

 

 

카운팅 정렬을 검색하면 Counting Array를 만든 뒤 이를 누적합으로 바꾼 뒤 원래 배열의 값을 하나씩 조회하고 1씩 빼주는 방식이 나오는데,

해당 방식은 정렬의 안정성을 보장하는 방식이므로 이 문제처럼 불안정 정렬로 충분할 땐 만들어진 Counting Array를 바로 이용하면 된다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(10001);
  
  for(int i=0;i<n;i++){
    int t;
    
    cin >> t;
    
    v[t]++;
  }
  
  for(int i=1;i<=10000;i++){
    for(int j=0;j<v[i];j++)  cout << i << "\n";
  }
  
  return 0;
}