문자열 뒤집기 문제

세그멘테이션 폴트에서 가져온 문자열 뒤집기 문제입니다.

문제 1.
본인에게 가장 편한 프로그래밍 언어로 문자열의 순서를 뒤집는 함수를 만드시오.

이 문제에 대한 해법은 몇 가지가 나올 수 있는데, 우선 문제의 정의에 따라 간단히 구현해 본다면...

/* 답: A안 */

void reverse(const char* text, char* out_buff, size_t max_length)
{
    const int src_length = strlen(text);
    int length = src_length < max_length ? src_length : max_length;

    for (int i = length-1; i >= 0; --i)
        *out_buff++ = text[i];

    *out_buff = NULL;
}

가장 심플하고 확실한 방법이긴 하지만, 사전에 메모리 공간을 할당받아야 된다는 것과 잘못된 메모리 접근으로 인한 오류의 가능성도 내포하고 있습니다.

물론, 메모리를 새로 할당받지 않고 그 자리에서 순서를 뒤집을 수 있는 방법도 있습니다.

/* 답: B안 */

template<typename T>
inline void swap(T& __a, T& __b)
{
    T __tmp = __a;
    __a = __b;
    __b = __tmp;
}

char* reverse(char* text)
{
    const int length = strlen(text);

    for (int i = length-1; i > 0; --i)
        for (int j = 0; j < i; ++j)
            swap(text[j], text[j+1]);

    return text;   
}

이 방법은 if문이 빠졌다는 것을 제외하면 버블 정렬과 모양새가 많이 비슷합니다. 그리고 여기에다는 쓰지 않았지만, 2번 문제에 대한 답도 이런 형태입니다.

하지만... 1번 문제를 풀면서 처음부터 이런 알고리즘으로 구현할 생각이었다면 최악의 선택이라고 감히 말할 수 있습니다. 말할 것도 없이, 이 알고리즘은 쓸데없이 많은 루프를 돌기 때문입니다.

자, 그럼 조금 다듬어 보기로 합시다.

/* 답: C안 */

template<typename T>
inline void swap(T& __a, T& __b)
{
    T __tmp = __a;
    __a = __b;
    __b = __tmp;
}

char* reverse(char* text)
{
    const int maxCnt = strlen(text) / 2;

    for (int i = 0; i < maxCnt; ++i)
        swap(text[i], text[length - i - 1]);

    return text;
}

문자열 뒤집기라는 것은 sort에서와는 달리 비교를 통해서 자리바꿈 하는게 아니라 처음부터 옮겨야할 자리가 정해져 있습니다. 게다가 서로 대칭되는 위치로 자리 바꿈만 하면 되는 겁니다.

예를 들어, "123456789"라는 문자열을 뒤집는다고 하면...

1 ↔ 9
2 ↔ 8
3 ↔ 7
4 ↔ 6
5는 제자리

결국 문자열 길이의 절반 만큼만 루프를 돌면 됩니다.

문제에서는 문자열 뒤집기를 다루고 있지만, 문자열도 결국은 배열. 좀 더 일반화시키면 어떤 종류의 배열도 순서를 뒤집어 볼 수 있습니다.

/* C안의 일반화: 배열 뒤집기 */

template<typename T>
inline void swap(T& __a, T& __b)
{
    T __tmp = __a;
    __a = __b;
    __b = __tmp;
}

template<typename T>
T* reverseArr(T* src, size_t length)
{
    const int maxCnt = length / 2;
   
    for (int i = 0; i < maxCnt; ++i)
        swap(src[i], src[length - i - 1]);
   
    return src;
}