[algospot/알고리즘] 알고스팟, '왕초보' 난이도 LECTURE 풀기

학부시절 알고리즘 강좌의 시작은 소팅이었습니다.

교수님은 한 주 정도 소팅에 대한 강의를 해주시고,

7~8가지 소팅 알고리즘을 코딩과제를 내주셨죠.

아주 흥미로운 과제였지만 동시에 지긋지긋하기도 했습니다.

'이걸 과연 어디에 써먹을까?'라고 생각도 했었는데요,

그걸 여기에 써먹게 되는군요.

현업에서 소팅알고리즘을 직접 짤 일은 거의 없습니다만,

결국엔 다 피가 되고 살이 된다고 믿고 싶습니다.

algopost에 실린 '왕초보'문제에 도전하겠습니다.

난이도는 '왕초보'인데 소팅 항목이 있어서 많은 생각을 하게 합니다.

소팅에 사용할 수 있는 최적화 알고리즘이 여러가지가 있겠습니다만,

순전히 감에 의존하여 발로 짠 답안을 공개하도록 하겠습니다. :)

문제는 영어로 되어 있어서 간단하게 한글로 의역했습니다.

문제에 소녀시대학교는 Sonyusi University입니다.

- 제목 : LECTURE

- 난도 : ★★☆☆☆ (2점/5점)

- 문제 : Lew 교수는 소녀시대학교에서 알고리즘을 가르치고 있습니다. 첫 해라 강의노트를 만드는데 많은 시간을 들이고 있죠. 다음 시간에 가르칠 recursion과 sorting를 위해 예제를 만들었는데, 그 중 하나가 무척 어렵다는 것을 알아차렸습니다. 스트링을 소팅하는 문제인데 절차는 아래와 같습니다.

1. 본래의 스트링을 2n이라고 할 때, n개로 쪼개어 각각 2글자로 만듭니다.

2. n개를 사전순으로 소팅합니다.

3. 모두 붙여서 출력합니다.

abbaaccb → ab ba ac cb → ab < ac < ba < cb → abacbacb

- 답안

#include <stdio.h>
#include <string.h>

#define FIXED_STRING_SIZE 2



static void _swap_fixed_string(char *a, char *b)
{
    int i = 0;
    char tmp[FIXED_STRING_SIZE] = {0, };

    for (i = 0; i < FIXED_STRING_SIZE; i++) {
        tmp[i] = a[i];
    }

    for (i = 0; i < FIXED_STRING_SIZE; i++) {
        a[i] = b[i];
    }

    for (i = 0; i < FIXED_STRING_SIZE; i++) {
        b[i] = tmp[i];
    }
}



static int _compare_fixed_string(char *a, char *b)
{
    int i = 0;
    int tmp = 0;

    for (i = 0; i < FIXED_STRING_SIZE; i++) {
        tmp = a[i] - b[i];
        if (tmp) return tmp;
    }

    return tmp;
}



static void _rebuild_heapsort(char *string, int root, int length)
{
    int changed = root;
    int left = (root << 1) + FIXED_STRING_SIZE;
    int right = (root << 1) + (FIXED_STRING_SIZE << 1);

    if (left < length
        && _compare_fixed_string(&string[changed], &string[left]) < 0)
    {
        changed = left;
    }

    if (right < length
        && _compare_fixed_string(&string[changed], &string[right]) < 0)
    {
        changed = right;
    }

    if (changed != root) {
        _swap_fixed_string(&string[root], &string[changed]);
        _rebuild_heapsort(string, changed, length);
    }
}



static void _build_heapsort(char *string, int length)
{
    int remainder = length % (FIXED_STRING_SIZE << 1);
    int i;
   
    if (remainder) {
        i = (length - FIXED_STRING_SIZE) >> 1;
    } else {
        i = (length - (FIXED_STRING_SIZE << 1)) >> 1;
    }

    for (; i >= 0; i -= FIXED_STRING_SIZE) {
        _rebuild_heapsort(string, i, length);
    }
}



static void _sort_string(char *string, int length)
{
    int i = 0;
    
    _build_heapsort(string, length);

    for (; i < length; i += FIXED_STRING_SIZE) {
        int last = length - i - FIXED_STRING_SIZE;
        _swap_fixed_string(string, string + last);
        _rebuild_heapsort(string, 0, last);
    }
}



int main(int argc, char **argv)
{
    register int i = 0;
    int count = 0;

    scanf("%d", &count);

    for (; i < count; i++) {
        char string[1001] = {0, };
        int length = 0;

        scanf("%s", string);
        if (!string) continue;

        length = strlen(string);
        if (!length) continue;

        _sort_string(string, length);

        printf("%s\n", string);
    }

    return 0;
}

- 문자열을 색다르게 소팅하고 싶어서 "굳이" heap sort를 사용하였습니다.

   _build_heapsort()에서 문자열을 heapsort 요건에 맞게 변환하였습니다.

   부모 노드 값이 자식 노드 값보다 크도록 정렬하고,

   root를 뽑아 제일 뒤로 옮깁니다.

   그리고 다시 heap sort에 맞게 재정렬하지요.

   _rebuild_heapsort()로 재정렬합니다.

   build & rebuild 과정은 아래 사이트에서 play 해보시면 도움이 될 겁니다.

   https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

- 문제에서는 두 글자의 스트링이라 한정했지만,

   코드를 짜다보니, "2"로 코드를 제한하기 싫어서,

   FIXED_STRING_SIZE를 정의하여 두 글자가 아닌 경우에도 적용할 수 있도록 하였습니다.

- 가급적이면 stdio 외에는 사용하고 싶지 않았는데,

   strlen()는 그냥 사용했습니다.

   귀차니즘이 문제네요.

  

순위는 2252위가 되었습니다.

4문제에서 하나 더 푸니 2626위에서 2252위로 374계단 올랐습니다.

이번 문제는 그간 사용해볼 기회가 없었던 heap sort를 사용한 것에 의미를 두겠습니다.

그럼 좋은 하루 보내세요~

* References

http://www.sorting-algorithms.com/

https://algospot.com/judge/problem/read/LECTURE

https://www.cs.usfca.edu/~galles/visualization/HeapSort.html