문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
코드
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
int main(void) {
int N;
int arr[10001] = { 0, };
scanf("%d", &N);
for (int i = 0; i < N; ++i) {
int a;
scanf("%d", &a);
arr[a]++;
}
for (int i = 0; i < 10001; ++i) {
for (int j = 0; j < arr[i]; ++j) {
printf("%d\n", i);
}
}
}
이 문제는 꽤 신박하다. N의 최대수가 10^7으로 꽤 큰 편에 추가적인 조건으로 수들이 10000보다 작거나 같은 숫자들이라 한다.
O(nlogn)의 시간복잡도로 풀면은 꽤 아슬아슬하게 갈 것 같긴 하지만 이 방법은 좀 아닌듯하다...
또한 N의 크기로 볼 때 저 어마어마한 숫자들을 다 저장하면 메모리 초과가 나올 것이다.
그렇다면 10000보다 작거나 같다는 조건을 사용해야 할텐데.... 이 문제의 힌트로 Counting sort라는 것을 보았다.
그래서 Counting Sort를 구글링하여 찾아본 결과 처음보는 정렬을 볼 수 있었고 바로 코딩하여 해봤지만 메모리 초과가 나왔다....
(counting sort 참고 : https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html)
그래서 다시 구글링해 본 결과 그냥 단순한 알고리즘이었던 것이다....
나온 횟수를 배열에 저장하여 인덱스 순서대로 다시 출력하면 되는 간단한 알고리즘이었다.
다만 이 정렬알고리즘은 숫자들의 최대 크기(여기선 10000)에 종속되기 때문에 최대 크기가 작을때만 성공 적으로 동작 할 수 있다.
'PS > 기타 알고리즘' 카테고리의 다른 글
[백준 / 11650] (C++) 좌표 정렬하기 (0) | 2022.06.19 |
---|---|
[백준 / 1427] (C++) 소트인사이드 (0) | 2022.03.26 |
[백준 / 2108] (C++) 통계학 (2) | 2022.03.20 |
[백준 / 2750] (C++) 수 정렬하기 (0) | 2022.03.18 |
[백준 / 2751] (C++) 수 정렬하기 2 (0) | 2022.03.18 |