[백준 15688] 수 정렬하기 5

15688번: 수 정렬하기 5 (acmicpc.net)

15688번: 수 정렬하기 5

 

배운것

수의 범위가 어느 정도 한정적일 때에만 Counting Sort를 쓸 수 있음

수의 범위가 대략 1000만 이하일때에는 카운팅 소트를 쓰고 그렇지 않을 경우에는 카운팅 소트를 쓰지 못한다고 생각하기

 

- 수가 -1,000,000에서 1,000,000인게 껄끄러우니 freq 배열의 인덱스에 접근할 때는 13번째 줄 처럼 100만을 더하고

freq 배열의 값을 보며 수를 출력할 때는 100을 빼준다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;

int freq[2000001];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
    int a;
    cin >> a;
    freq[a+1000000]++;
  }
  for(int i = 0; i <= 2000000; i++){
    while(freq[i]--){ // cnt[i]번 반복
      cout << i-1000000 << '\n';
    }
  }
}