티스토리 뷰

/*

백준 [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
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
TAG
more
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함