https://www.acmicpc.net/problem/10989
정수를 정렬하는 문제. 수 정렬하기2(https://www.acmicpc.net/problem/2751)는 시간을 적게준 대신에 메모리는 넉넉하게 줬다면, 이번에는 시간을 좀 널널하게 주는 대신에 메모리를 확 줄여버린 문제이다. 처음에는 그게 무슨상관이지? 했는데, 메모리를 적게 준데에는 다 이유가 있었던거 같다.
수 정렬하기 2도 퀵소트로 풀려다가 못풀어서 결국 C의 stdlib헤더의 qsort와 C++의 std::sort로 겨우 풀긴 했었지만, 이번에는 그것도 먹히지 않는다. 아무래도 다른 정렬알고리즘로 해결을 해야 할 것 같다.
// C
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b)
{
int num1 = *(int *)a;
int num2 = *(int *)b;
if (num1 < num2) return -1;
if (num1 > num2) return 1;
return 0;
}
int main () {
int * arr = NULL;
int len;
scanf("%d", &len);
arr = (int *)malloc(sizeof(int) * len);
for (int i = 0; i < len; i++)
scanf("%d", &arr[i]);
qsort(arr, len, sizeof(int), compare);
for (int i = 0; i < len; i++)
printf("%d\n", arr[i]);
free(arr);
}
// C++
#include <iostream>
#include <algorithm>
using namespace std;
int main () {
int * arr;
int len, i;
cin >> len;
arr = new int[len];
for (i = 0; i < len; i++) cin >> arr[i];
sort(arr, arr+len);
for (i = 0; i < len; i++) cout << arr[i] << '\n';
}
-------------------------------------------------- 21. 11. 23 --------------------------------------------------
기존의 방식으로 해결을 하는 경우 메모리가 초과가 되었다. 기존의 방식은 일단 입력받은 모든 수를 저장을 한 후에, 정렬을 하는 방식이었기 때문이다. 검증케이스에는 최대 천만개의 정수가 들어오게 되는데, 이때 이 수를 모두 저장하는 경우, 4천만 바이트, 약 40MB를 수를 저장하는데 사용하게 된다. C계열의 메모리 제한이 8MB임을 보면, 기준치를 5배나 넘기는 셈이다. 이러니 메모리가 초과될 수 밖에...
이러한 문제를 어떻게 해결할까 하다가, 단계별 풀이의 힌트(https://www.acmicpc.net/step/9)를 보고 카운팅 정렬이라는 알고리즘을 알게 되었다. 카운팅정렬의 큰 틀은, 입력받은 수를 저장하는게 아니라, 몇번 등장했는지를 저장하여, 등장횟수의 배열을 누적합으로 바꾸고, 이를 이용하여 정렬하는 알고리즘이다.
이 알고리즘에서 방법을 착안하여, 필자는 숫자들의 등장횟수만을 세고, 반복문을 돌면서, 등장횟수만큼 숫자를 출력하는 방식으로 해결했다. 굳이 누적합을 하여 재배열하는 단계가 필요없을 것이라고 판단했기 때문이다.
이 방식의 단점은, 갑자기 큰수가 확 나와버리면 무의미한 반복문을 돌기 때문에 입력되는 숫자의 범위를 잘 보아야 한다.
#include <stdio.h>
#define SIZE 10000
int main () {
int count[SIZE] = {0};
int t, input;
scanf("%d", &t);
while(t--) {
scanf("%d", &input);
count[input-1]++;
}
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < count[i]; j++) {
printf("%d\n", i+1);
}
}
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 1009번 C언어 풀이 (0) | 2021.11.11 |
---|---|
백준 10845번 C언어 풀이 (0) | 2021.11.11 |
백준 10828번 C언어 풀이 (0) | 2021.11.04 |
백준 1011번 C언어 풀이 (0) | 2021.11.01 |
백준 2609번 C언어 풀이 (0) | 2021.10.27 |