문제
염라대왕은 이승의 사람들의 모든 이름을 가지고 있다.
어느날 저승에 일어난 진도 8.0 지진에 항상 정리되어 있던 이승 명부가 흐트러졌다.
이승 명부는 이름의 길이가 짧을수록 이 앞에 있었고, 같은 길이면 사전 순으로 앞에 있었다.
이왕 이렇게 된 김에 모든 이름을 다시 정리하고 같은 이름은 하나만 남겨놓기로 한 염라대왕을 도와주자.
[입력]
첫 번째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 50)가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 이승 명부의 이름 개수 N(1 ≤ N ≤ 20,000)이 주어진다.
각 테스트 케이스의 두 번째 줄부터 N개의 줄에 걸쳐서 알파벳 소문자로 이루어진 이름들이 주어진다.
이름에는 공백이 포함되지 않으며 최소 1개, 최대 50개의 알파벳으로 이루어져 있다.
[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,
정리된 이름을 한 줄에 하나씩 출력하라. 같은 이름은 한 번만 출력해야 하는 것을 주의하라.
코드
#include <iostream>
#define N 20000 // 원하는 원소의 갯수
using namespace std;
void mergeSort(string arr[], int size)
{
if (size == 1) return;
int mid = size / 2;
// mid를 기준으로 나눈 좌, 우 배열 2개를 분할
mergeSort(arr, mid);
mergeSort(arr + mid, size - mid);
string* buf = new string[size];
int i = 0, j = mid, k = 0;
// 좌 우 배열 비교하면서 임시 buf 배열에 정렬하여 저장
while (i < mid && j < size)
{
if (arr[i].size() == arr[j].size())
{
buf[k++] = (arr[i] < arr[j]) == true ? arr[i++] : arr[j++];
}
else
{
buf[k++] = arr[i].size() < arr[j].size() ? arr[i++] : arr[j++];
}
}
// 좌 배열만 남은 경우
while (i < mid)
{
buf[k++] = arr[i++];
}
// 우 배열만 남은 경우
while (j < size)
{
buf[k++] = arr[j++];
}
// 정렬을 마친 후 arr에 저장
for (i = 0; i < size; i++)
{
arr[i] = buf[i];
}
delete[] buf;
}
int main()
{
int t, n;
string s;
cin >> t;
for (int a = 1; a <= t; a++)
{
string arr[N];
cin >> n;
for (int b = 0; b < n; b++)
{
cin >> s;
arr[b] = s;
}
mergeSort(arr, n);
cout << "#" << a << '\n';
for (int b = 0; b < n; b++)
{
if (arr[b] != arr[b + 1])
{
cout << arr[b] << '\n';
}
}
}
return 0;
}설명
이 문제는 분할정복의 개념을 이해하고 적용하기에 매우 적합한 문제이다.
전체 크기의 중간지점인 mid를 기준으로 좌 우 2개로 나누어 배열 2개를 만든다.
이 과정을 원소가 1개일 때까지 반복하여 나누어준다.
좌 우 배열을 비교하면서 임시 buf 배열에 조건에 맞게 정렬하여 저장한다.
ex)
1, 2, 3, 4, 5, 6, 7, 8
1-2, 3-4, 5-6, 7-8
1-2-3-4, 5-6-7-8
1-2-3-4-5-6-7-8
후기
개념을 배우자마자 풀기에는 난이도가 있는 문제였다.
재귀함수를 이용해서 최소단위로 쪼개주고 난 후에
좌 우 배열을 비교하면서 조건에 맞게 정렬하여 임시 buf 배열에 저장하고
남아있는 하나의 배열까지 옮겨주면 arr에 저장하게 되는 과정의 흐름은 잘 파악했지만
다시 처음부터 구현하라고 하면 시간이 오래걸릴 것 같다.. 복습 잘하자
