문제
Professor Lew teaches Algorithm course in Sonyusi University (소녀시대학교).
It is his first year as a professor, so he spends a lot of time making lecture notes.
He'll teach recursion and sorting algorithms in the next class,
and he wants to make some examples which will be included in his lecture note.
While making some examples for his lecture note, he noticed that one of his work was quite difficult.
The example was for sorting a string, and the exact process was as follows:
First, the original string of length 2n is divided into n substrings, each of length 2.
Then sort the n strings in lexicographic order, and then concatenate them to obtain the result string.
Note that the sorting process will be performed on n strings, but not each of the n strings.
The following example illustrates the process:
abbaaccb → ab ba ac cb → ab < ac < ba < cb → abacbacb
Since the process was quite confusing,
professor Lew decides to use a computer program for verification.
Given an alphabetic string of even length, write a program that prints the result of the sorting process.
입력
The first line of the input contains one integer T, the number of test cases.
The first line of each test case contains a string. The length of the string will not exceed 1000, and will only contain lowercase alphabet letters.
출력
For each test case, print the result in one line.
예제 입력
4 abbaaccb dddcccbbbaaa geegeegeegeebabybabybaby oh
예제 출력
abacbacb aababbccdcdd babababybybyeeeeegeggege oh
2n 의 길이를 갖는 문자열을 입력 받아 정렬하는 문제 입니다. 문제에 나와 있는 예제대로
abbaaccb → ab ba ac cb → ab < ac < ba < cb → abacbacb
2자리 씩 나눠서 앞자리 순으로 정렬 후 같은 알파벳 끼리 뒷자리를 기준으로 정렬합니다. 저는 가장 간단하고 많은 분들이 생각 해보셨을 것 같은 버블정렬을 이용하여 문제를 풀었습니다. 먼저 앞자리 알파벳으로 버블정렬 수행 후, 같은 자리 끼리 뒷자리 알파벳을 비교하여 정렬을 수행 했습니다.
가장 빠른 처리속도 분들의 소스를 봐보니 기수정렬을 이용해서 풀었더군요. 버블정렬보다 훨씬 간단하고 빨라 보입니다.
혹시 기수정렬에 대해 모르시는 분들을 위해 간단하게 말씀드리고 자세한 내용은 따로 올리도록 할게요.
다른 분들의 소스 중 하나를 살펴볼게요.
먼저 첫 포문에서 cnt 배열을 초기화 하는데 이는 알파벳을 체크하기 위한 배열로 보입니다. 배열의 크기가 32인 이유는 잘 모르겠네요...
while문에서 해당하는 알파벳의 카운트를 해줍니다. 인덱스 값으로 -97을 해주는데 이는 ASCII 코드에 나오는 알파벳들의 값을 인덱스로 하여 집어넣어 주기 위합입니다.
예를 들어 소문자 a 는 10진수로 97이라는 값을 갖습니다. -97 을 모든 알파벳에 적용한다면 인덱스 0 의 자리 부터 a b c . . . 순으로 인덱스 값을 갖게 되겟죠.
다음으로 나오는 for문에서는 알파벳의 정렬 순서와 알파벳 위치를 설정하는 구문입니다.
전체적인 포문이 d = 1 , 0 순으로 실행됩니다. 이는 2자리 씩 끈은 알파벳 자리에서 뒷 자리 부터 비교하겠다는 의미가 됩니다.
dcba 라는 문자열을 입력 했을 경우 cnt배열은
첫번째로 c 와 a 를 비교하여
01122222... 라는 숫자 열을 갖게 됩니다.
여기서 0 1 2 라는 숫자는 각 알파벳이 표시되어야 하는 순서와 표시될 위치를 의미하죠.
0 1 1 2 2 2 2..
a c
순으로 표시 정보를 의미합니다.
두번째로 d b 를 비교하여
00112222... 라는 열이 나오고
위와 마찬가지의 정보를 가집니다.
각 cnt 배열 정보값을 이용하여 마지막 구문에서 표시를 해주면 정렬된 문자열이 표시됩니다.
'알고리즘 > Algospot' 카테고리의 다른 글
| 튜토리얼 [ENCRYPT] (0) | 2016.07.11 |
|---|
_Able