티스토리 뷰
/*
백준 [10989번] 수 정렬하기3
분류 : 정렬
비슷한 문제 : 2750번 수 정렬하기, 2751번 수정렬하기2
문제 풀기 : quick sort 사용 오름차순 정렬로 풀려고 했으나 overflow가 남
그래서 DB시간에 배운 index를 활용하여 품
주의 사항
arr의 배열이 int당 4byte라 치면 40,000,000byte -> 39062kbyte -> 38mb라는 큰 메모리를 요구하게 된다
*/
/*
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include<stdlib.h>
void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void quick_sort(int* array, int start, int end) {
if (start >= end) return;
int mid = (start + end) / 2;
int pivot = array[mid];
swap(&array[start], &array[mid]);
int p = start + 1, q = end;
while (1) {
while (array[p] <= pivot) { p++; }
while (array[q]>pivot) { q--; }
if (p>q) break;
swap(&array[p], &array[q]);
}
swap(&array[start], &array[q]);
quick_sort(array, start, q - 1);
quick_sort(array, q + 1, end);
}
int main(void) {
int array[10000002];
int i;
int n;
scanf("%d", &n);
//array = (int*)malloc(sizeof(int)*n);
for (i = 0; i<n; i++) {
scanf("%d", &array[i]);
}
quick_sort(array, 0, sizeof(array) / sizeof(int) - 1);
for (i = 0; i<n; i++) {
printf("%d\n", array[i]);
}
return 0;
}
*/
// 위의 코드는 퀵소트 오름차순으로 풀었던 것
#include <stdio.h>
#define INDEX 10001
int main()
{
int n, i, j, k;
int arry[INDEX] = { 0, };
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d", &k);
arry[k] = arry[k] + 1;
}
for (i = 1; i < INDEX; i++)
{
if (arry[i] != 0)
{
for (j = 0; j < arry[i]; j++)
printf("%d\n", i);
}
}
}
// 아래의 코드는 n의 값을 받고 들어오는 값의 범위가 10000 이하의 숫자라는 것을 힌트로 시작한다.
// n번의 loop에서 값을 받고 그 값에 해당하는 arr[ 받은 값 ] 에 해당하는 곳의 배열에 1을 더해줌으로써 들어온 값에 대한 분포를 알 수 있고 이미 배열은 순차적으로 정렬이 되어 있기에 바로 출력하면 된다.
// 또한 마지막 arr[i] != 0 이라는 코드는 자신이 받지 않은 코드에 대해 걸러주는 역할을 함으로써 출력을 할 수 있다.
// 시간 복잡도는 n 시간이 걸리는 scan 이라는 방식을 쓰고 있다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
기본적 정렬 (0) | 2017.03.14 |
---|---|
쿼드트리란? (0) | 2017.03.13 |
백준[3047번] ABC (0) | 2016.12.06 |
개구리 뛰기(codeground) (0) | 2016.11.26 |
균일수(codeground) (0) | 2016.11.26 |