[백준 알고리즘] 10989번: 수 정렬하기 3
May 05, 2020
10989번: 수 정렬하기 3
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.접근 방법:
- 접근 방법 1: 문제에서 카운팅 정렬을 사용하라는 힌트를 주어서 구글링을 통해 카운팅 정렬의 개념을 보고 구현에 성공 했다. 근데 메모리 초과 오류가 났다. 이 문제에서 메모리가 8MB로 제한되어 있기 때문에 배열을 3개까지 사용해야하는 카운팅 정렬은 불가능 했다.
- 접근 방법 2: 자연수가 10000까지 들어오므로 배열을 하나만 써서 해결해야한다. 카운팅 정렬의 컨셉만 그대로 사용해서 입력을 받을 때마다 입력을 따로 저장하지 않고 몇번 나왔는지 출현 횟수만 저장하는 카운팅 배열 하나만 사용한다. 그리고 입력이 모두 끝난 이후에는 배열의 처음부터 끝까지 순회하면서 숫자 N을 출현했던 횟수 coutn[N] 만큼 출력해준다. 이렇게 하면 배열을 하나만 쓰고 해결 할 수 있다.
통과 코드:
#include<iostream>
#include<vector>
using namespace std;
int main (){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
vector<int> outarr (10001, 0);
while(N--){
int n;
cin >> n;
// 입력을 받을 때마다 배열에 카운팅 개수 늘려주기
outarr[n]++;
}
// 여기 까지 왔을 때는 각 배열의 인덱스에 해당하는 값이 몇번나왔는지 배열에 들어가 있다.
for (int i = 0 ; i < outarr.size() ; i++){
while(outarr[i] != 0){ // 카운팅이 0이 될 때까지 출력
cout << i << "\n";
outarr[i]--;
}
}
return 0;
}
