BOJ 백준 10989 : 수 정렬하기 3
Updated:
시작하면서
이번 문제는 계수 정렬(counting sort) 카테고리 문제이다. 계수 정렬은 개념을 공부하고, 직접 구현해서 문제 풀이에 적용하려고 한다.
개념
계수 정렬(counting sort)은 정렬 알고리즘으로 O(n)의 시간 복잡도를 갖는다. 좀 더 정확히 말하자면 O(n+k)인데 여기서 k는 정렬할 수들 중에 가장 큰 값을 의미한다. 예를 들어, n = 10, k = 100 일 경우에는 O(n + n^2) 이므로 O(n^2)이 된다. 즉, 정렬할 수들의 최대 값에 영향을 받는 알고리즘이라고 할 수 있다.
예제를 통해서 알고리즘을 알아보자.
A = [2, 0, 2, 0, 4, 1, 5, 5, 2, 0, 2, 4, 0, 4, 0, 3]
위와 같은 A를 counting sort 해보자. 먼저 A의 모든 요소 값의 빈도를 특정 배열(Counting Array) C에 저장한다.
C = [5, 1, 4, 1, 3, 2]
C의 각 index에 들어 있는 값들은 각 index가 A에 몇 개가 들어 있는지를 의미한다. ex) C[0] : A에 0이 몇개 들었는지 . . .
다음은 C의 각 요소 값에 직전 인덱스의 값을 더해서 업데이트 해준다.
C = [5, 6, 10, 11, 14, 16]
A와 같은 크기를 갖는 배열(output) B를 만든다. 처음에는 비워둔다.
우선 배열 C의 index의 의미들을 알고 가자
- [c0 = 5] : 0은 b1에서 b5까지 총 5개의 자리를 차지한다.
- [c1 = 6] : 1은 b6 한 개 자리를 차지한다.
- [c2 = 10] : 2는 b7에서 b10까지 네 개 자리를 차지한다.
- [c3 = 11] : 3은 b11 한 개 자리를 차지한다.
- [c4 = 14] : 4는 b12에서 b14까지 세 개 자리를 차지한다.
- [c5 = 16] : 5는 b15에서 b16까지 두 개 자리를 차지한다.
이제 C 배열의 의미대로 B 배열을 만들면 된다. 첫 인덱스부터 차례대로 넣어준다.
B = [0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 3, 4, 4, 4, 5, 5]
문제 이해
문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 2가지이다.
-
N : 주어질 수의 개수
-
주어지는 수
이 변수를 가지고 답을 출력해야 한다.
문제 아이디어
여러 정렬을 이용할 수 있겠지만, 계수 정렬을 공부하기 위한 문제이므로 계수 정렬을 사용해서 해결하려고 한다. 계수 정렬은 N의 크기가 클수록 비효율적인데, 해당 문제는 N의 최대가 10000이므로 사용해도 무방한 작은 크기이다.
해결
#include <iostream>
using namespace std;
#define MAX_NUM (10001)
void Input();
void PrintAnswer();
int N;
int countingArray[MAX_NUM];
int main()
{
// sync off
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
Input();
PrintAnswer();
}
void Input()
{
int value;
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> value;
countingArray[value]++;
}
}
void PrintAnswer()
{
for (int i = 1; i < MAX_NUM; i++)
{
if (countingArray[i] == 0)
{
continue;
}
for (int j = 0; j < countingArray[i]; j++)
{
cout << i << "\n";
}
}
}
코드를 보면 알겠지만, 위에서 공부한대로 계수 정렬을 사용하지는 않았다. 해당 문제에서는 메모리와 수행 시간을 줄여야해서 쓸데없는 사족은 전부 제외했다.
input을 받자마자 countingArray의 해당 index에 값을 증가시켜서 따로 array를 더 만들지 않았고, 답을 출력할 때 index들의 값만큼 각 array 값을 출력해서 문제를 해결했다.
마치며
학부 시절에 공부하고 쓸 일이 거의 없어서 공부하지 않았던 부분이었는데, 이렇게 복습하니 기억도 새록새록 나고 재밌는 파트였다. 실전에서 쓸 일이 생기면 적용해봐야겠다.
Leave a comment