문제는 매우 단순합니다.
N을 입력받아 N번 숫자를 입력받은 후 오름차순으로 정렬하는 문제입니다.
하지만 제한시간이 2초라는 점을 감안해야 할 것 같습니다.
시간이 짧으므로, 시간 복잡도가 작은 기수 정렬 (radix sort) 를 활용해 문제를 풀어보겠습니다.
백준_10845_큐(queue)
큐를 구현하는 문제입니다. 큐의 개념)큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO)의 형태를 가지고 있습니다. 나중에 넣은 데이터가 먼저 나오는 스택과는 정반대의 성질을 지니고
sol248.tistory.com
바로 이전에 큐 문제를 푼 적이 있습니다. 이 문제도 원형 큐를 이용한 기수정렬로 풀 것이기에,
큐에 대해 모르시는 분은 10845_큐 문제를 먼저 보고 오시는 것을 추천드립니다.
기수정렬 (radix sort) 의 개념 )
문제를 풀기 전에, 기수 정렬이 뭔지 알고 가야겠죠.
기수 정렬이란, 자리수별로 비교 없이 수행하는 정렬 알고리즘입니다.
비교 연산이 없기 때문에 정렬 속도가 매우 빠르지만, 데이터 전체 크기만한 메모리가 더 필요하다는 단점이 있습니다.
정렬 과정)
이제, 정렬 방식을 살펴보죠. 다음과 같은 array 정수 배열이 있습니다.
int array[10] = { 91, 19, 34, 202, 55, 15, 9, 119, 1, 22 }
가장 큰 숫자가 3자리 수이므로, 정렬 과정은 3번 반복합니다.
왜 3번 반복인지는 과정을 다 보시면 알 수 있습니다.
아래 표는 큐(queue) 를 표현한 것입니다.
1번째. -> 1의 자리수에 따라 정렬합니다. ( 1의 자리수가 1이면 1번 인덱스. .. . )
| 91 1 |
202 22 |
34 | 55 15 |
19 9 119 |
|||||
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
2번째 -> 1번째에 이어 10의 자리수에 따라 정렬합니다.
| 1 202 9 |
15 19 119 |
22 | 34 | 55 | 91 | ||||
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
3번째 -> 2번째에 이어 100의 자리수에 따라 정렬합니다.
| 1 9 15 19 22 34 55 91 |
119 | 202 | |||||||
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
3번째까지의 과정이 끝났습니다.
보시다시피 정렬이 완료된 것을 확인할 수 있습니다.
이제 차례대로 꺼내주기만 하면 정렬이 완료되겠죠.
이제 코드로 구현해 봅시다.
큐의 push, pop 함수)
push , pop 함수가 이해가 안되신다면 위의 큐 문제를 보고 오시는 것을 추천드립니다.
#define N 1000000
int queue[N];
int front = 0, rear = 0;
int push(int k)
{
if ((rear + 1) % N == front)
{
return -1;
}
else
{
queue[rear] = k;
rear++;
rear %= N;
return 1;
}
}
int pop()
{
int k;
if (front == rear)
{
return -1;
}
else
{
k = queue[front];
queue[front] = 0;
front++;
front %= N;
return k;
}
}
radixSort(기수정렬) 함수 )
void radixSort(int arr[], int size)
{
int factor = 1;
int max = 0;
int digit = 0;
for (int i = 0; i < size; i++)
{
if (arr[i] > 0)
{
if (arr[i] > max)
{
max = arr[i];
}
}
else if (arr[i] < 0) //음수의 자리수까지 파악하기 위해 절댓값 이용
{
if ((-1) * arr[i] > max)
{
max = arr[i] * (-1);
}
}
}
for (int i = max; i > 0;) //자리수 파악
{
i /= 10;
digit++;
}
for (int i = 0; i < digit; i++) //자리수만큼 반복
{
for (int j = 9; j >= 0; j--) //음수의 경우, -9~0 자리수 확인
{
for (int k = 0; k < size; k++)
{
if (arr[k] < 0 && (arr[k] / factor) % 10 == -j)
{
push(arr[k]); //자리수에 따라 작은 순서대로 queue에 push
}
}
}
for (int j = 0; j < 10; j++) //양수의 경우 0~9 자리수 확인
{
for (int k = 0; k < size; k++)
{
if (arr[k] >= 0 && (arr[k] / factor) % 10 == j)
{
push(arr[k]); //자리수에 따라 작은 순서대로 queue에 push
}
}
}
factor *= 10; //다음 자리수 확인을 위해 10 곱해주기
for (int p = front; p != rear; p++) //n번째 연산이 끝나면 큐의 데이터를 배열에 옮기고 큐 초기화
{
arr[p] = pop();
}
front = 0;
rear = 0;
}
}
이 문제에서는 입력되는 수가 절댓값이 1,000,000 보다 작거나 같은 정수이므로 음수까지 고려해서 코드를 작성했습니다.
음수를 먼저 찾아서 push한 다음, 양수를 push 하였습니다.
그리고, n번째 과정이 완료되면, 큐의 데이터들을 arr 배열에 옮겨담고 queue를 초기화한 후, 다음 과정을 실행합니다.
저도 며칠 전부터 하는건데, 코드가 잘 작동하는지 확인할 때, 그냥 실행해보는 것보다 디버깅 해보시는 것을 추천드립니다.
틀렸다거나, 오류가 날 때 디버깅을 해보면 어디가 잘못 작동하고 있는지 알 수 있다는 장점이 있습니다.
mac 환경 vscode 에서 C언어 개발환경 세팅 (feat.디버깅)
컴파일부터 디버깅까지
velog.io
저는 이 블로그 보고 vscode 에서 디버깅 하며 잘 쓰고있습니다. 디버깅 꼭꼭꼭 하시길 추천드립니다.
main 함수)
void print_arr(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d\n", arr[i]);
}
// printf("\n");
}
int main(void)
{
int n;
scanf("%d", &n);
int array[n];
for (int i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
int size = sizeof(array) / sizeof(int);
radixSort(array, size);
print_arr(array, size);
return 0;
}정렬,큐 모두 함수로 만들었기 때문에 메인 함수는 매우 간단합니다.
그냥 배열을 입력받아서 정렬 함수, 출력 함수만 실행시켜주면 됩니다.
생각하지 못한점)
하지만 미처 생각하지 못한 점이 있었습니다....
예제도 잘 작동하고, 질문 게시판에 있는 반례들을 입력해봐도 잘 작동하는데 도대체 왜 자꾸 틀렸다고 하는거지???
라는 생각을 오늘 하루종일 했습니다..
제가 이전에 원형 큐의 개념에 대해 설명했던 거 혹시 기억 나십니까??
원형 큐는 front 와 rear 의 값을 구분할 하나의 빈칸이 필요하다는거..
이 문제는 최대 1,000,000 개의 입력이 들어올 수도 있습니다.
그래서 제가 큐의 크기를 1,000,000 으로 설정하였죠.. ( #define N 1000000 ) 이렇게 말이죠.
그래서 방금 #define N 1000001 로 바꾸었더니 문제가 해결되었습니다...
정말... 사소한 것도 잘 신경써야 한다는 교훈을 다시 한번 얻었습니다..
전체 코드)
#include <stdio.h>
#define N 1000001
int queue[N];
int front = 0, rear = 0;
int push(int k);
int pop();
void radixSort(int arr[], int size);
void print_arr(int arr[], int size);
int main(void)
{
int n;
scanf("%d", &n);
int array[n];
for (int i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
int size = sizeof(array) / sizeof(int);
radixSort(array, size);
print_arr(array, size);
return 0;
}
int push(int k)
{
if ((rear + 1) % N == front)
{
return -1;
}
else
{
queue[rear] = k;
rear++;
rear %= N;
return 1;
}
}
int pop()
{
int k;
if (front == rear)
{
return -1;
}
else
{
k = queue[front];
queue[front] = 0;
front++;
front %= N;
return k;
}
}
void print_arr(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d\n", arr[i]);
}
// printf("\n");
}
void radixSort(int arr[], int size)
{
int factor = 1;
int max = 0;
int digit = 0;
for (int i = 0; i < size; i++)
{
if (arr[i] > 0)
{
if (arr[i] > max)
{
max = arr[i];
}
}
else if (arr[i] < 0) // 음수의 자리수까지 파악하기 위해 절댓값 이용
{
if ((-1) * arr[i] > max)
{
max = arr[i] * (-1);
}
}
}
for (int i = max; i > 0;) // 자리수 파악
{
i /= 10;
digit++;
}
for (int i = 0; i < digit; i++) // 자리수만큼 반복
{
for (int j = 9; j >= 0; j--) // 음수의 경우, -9~0 자리수 확인
{
for (int k = 0; k < size; k++)
{
if (arr[k] < 0 && (arr[k] / factor) % 10 == -j)
{
push(arr[k]); // 자리수에 따라 작은 순서대로 queue에 push
}
}
}
for (int j = 0; j < 10; j++) // 양수의 경우 0~9 자리수 확인
{
for (int k = 0; k < size; k++)
{
if (arr[k] >= 0 && (arr[k] / factor) % 10 == j)
{
push(arr[k]); // 자리수에 따라 작은 순서대로 queue에 push
}
}
}
factor *= 10; // 다음 자리수 확인을 위해 10 곱해주기
for (int p = front; p != rear; p++) // n번째 연산이 끝나면 큐의 데이터를 배열에 옮기고 큐 초기화
{
arr[p] = pop();
}
front = 0;
rear = 0;
}
}
여러분은 이런 실수 하지 않으시길 바랍니다..
'백준 > c' 카테고리의 다른 글
| 백준_2903_중앙이동알고리즘 (2) | 2024.05.03 |
|---|---|
| 백준_1934_최소공배수 (0) | 2024.05.01 |
| 백준_10845_큐(queue) (0) | 2024.05.01 |
| 백준_2775_부녀회장이될테야 (0) | 2024.04.28 |
| 백준_2869_달팽이는올라가고싶어 (2) | 2024.04.28 |