[BOJ] 2751번 : 수 정렬하기 (★)

🔒 문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

⌨ 입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

🖨 출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

📚 예제

Ex1)

5
5
4
3
2
1

1
2
3
4
5

📌 풀이

1. bubble sort 사용=> 시간 초과
2. 🔨 실패한 코드

int sort(int* ary, int N) { 
    int t; 
    for (int i = 0; i < N; i++) 
        for (int j = 1; j < N - i; j++) 
            if (ary[j - 1] > ary[j]) 
                SWAP(t, ary[j - 1], ary[j]); 
    return ary; 
}

3. radix sort 사용

🔨 실패한 코드 (radix sort)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define max 10
#define MALLOC(p,s)\
        if(!((p) = malloc(s))){\
            fprintf(stderr,"Insufficient Memory");\
            exit(EXIT_FAILURE);}

typedef struct queue* queuePointer;
typedef struct queue {
    int n;
    queuePointer link;
}queue;

queuePointer front[max], rear[max];

void add(int i, int n);
int delete(int i);
int queueEmpty();
void queueFull();

queuePointer makeQ(int n);

int radix_sort(int N, int* ary,int k);
int put(int N, int* ary);

void print(int N, int* ary);

int main()
{
    int N, M = 0; // N은 개수, M은 최대값 
    int k = 0; // k는 최대 자리 수
    scanf("%d", &N);
    int* ary = malloc(sizeof(int) * N);

    for (int i = 0; i < N; i++)
    {
        scanf("%d", &ary[i]);
        if (ary[i] > M)
            M = ary[i];
    }

    while (M != 0)
    {
        M /= 10;
        k++;
    }

    ary = radix_sort(N, ary, k);
    print(N, ary);

    return 0;
}

void add(int i, int n)
{
    queuePointer temp = makeQ(n);

    if (front[i])
        rear[i]->link = temp;
    else
        front[i] = temp;
    rear[i] = temp;

}
int delete(int i)
{
    int n;
    queuePointer temp = front[i];
    if (!temp)
        return queueEmpty();

    front[i] = temp->link;
    return temp->n;
}
int queueEmpty()
{
    printf("queue is Empty\n");
}
void queueFull()
{
    printf("queue is full\n");
}

queuePointer makeQ(int n)
{
    queuePointer temp;
    MALLOC(temp, sizeof(*temp));
    temp->n = n;
    temp->link = NULL;

    return temp;
}

int radix_sort(int N, int* ary, int k)
{
    int index; // front랑 rear 몇번째 인덱스에 들어갈지
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int a = pow(10, i + 1);
            int b = pow(10, i);
            index = (ary[j] % a) / b;

            add(index, ary[j]);
        }
        ary = put(N, ary);
    }
    return ary;
}
int put(int N, int* ary)
{
    queuePointer temp;
    int j = 0;
    for (int i = 0; i < 10; i++)
    {
        while (1)
        {
            temp = front[i];
            if (!temp)
                break;
            else
            {
                ary[j++] = temp->n;
                front[i] = temp->link;
            }
        }
    }
    return ary;
}

void print(int N, int* ary)
{
    for (int i = 0; i < N; i++)
        printf("%d\n", ary[i]);
}

=> 음수가 주어지는 경우를 생각 못해서,,,실패

3. quick sort=> 시간 초과,, 직접 짠 quick sort는 일부러 시간 복잡도 최악으로 나오게 수를 줘서 그런것 같습니다.
   수를 주는대로 배열에 넣는게 아니라 랜덤으로 배열에 넣으면 이런 일이 없을까요으,, 다시 해보겠습니다.
4. 🔨 실패한 코드

#include <stdio.h> 
#define SWAP(x,y,t)(t=x,x=y,y=t) 
int* ary;

void quicksort(int left, int right);
void print(int N);

int main() {
    int N;
    scanf("%d", &N);
    ary = (int*)malloc(sizeof(int) * N);

    for (int i = 0; i < N; i++)
        scanf("%d", &ary[i]); 

    quicksort(0, N);
    print(N);
    return 0;
}

void quicksort(int left, int right) {
    int pivot, i, j, t;
    if (left < right) {
        pivot = ary[left];
        i = left, j = right;
        do {
            do i++;
            while ((ary[i] < pivot) && (i < right));
            do j--;
            while ((ary[j] > pivot) && (j > -1));
            if (i < j)
                SWAP(ary[i], ary[j], t);
        } while (i < j);
        SWAP(ary[left], ary[j], t);
        quicksort(left, j);
        quicksort(j + 1, right);
    }
}

void print(int N) {
    for (int i = 0; i < N; i++)
        printf("%d\\n", ary\[i\]);
}

python으로 성공

import sys
N = int(sys.stdin.readline())
ary = []
for i in range(N):
    ary.append(int(sys.stdin.readline()))
ary.sort()
for i in range(N):
    print(ary[i])

🔑 python 코드

import sys
N = int(sys.stdin.readline())
ary = []
for i in range(N):
    ary.append(int(sys.stdin.readline()))
ary.sort()
for i in range(N):
    print(ary[i])

파이썬 만만세다