C 또는 C++에서 문자열을 제자리(In-place)에서 뒤집는 방법

이 글에서는 문자열을 제자리(in-place)에서 뒤집는 방법을 살펴보겠습니다. 제자리 방식이란 문자열을 뒤집을 때 별도의 추가 메모리 공간을 사용하지 않고, 기존 배열 안에서 직접 연산을 수행하는 것을 의미합니다. C++에서는 std::string을 활용할 수 있지만, C 언어에서는 반드시 문자 배열(character array)을 사용해야 합니다. 여기서는 문자 배열로 문자열을 입력받은 뒤 이를 뒤집는 과정을 구현해 보겠습니다.

입력: 문자열 "This is a string"
출력: 뒤집힌 문자열 "gnirts a si sihT"

알고리즘

reverse_string(str)

입력 − 뒤집을 문자열

출력 − 뒤집힌 문자열

핵심 아이디어는 두 개의 포인터(인덱스)를 사용하는 것입니다. 하나는 문자열의 시작 위치(i)를 가리키고, 다른 하나는 끝 위치(j)를 가리킵니다. 두 포인터가 서로 만나거나 교차할 때까지 양 끝의 문자를 서로 교환하며 안쪽으로 이동하면, 추가 메모리 없이 문자열 전체가 뒤집힙니다.

len := 문자열의 길이
i := 0, j := (len - 1)
while i < j, do
   위치 i와 j의 문자를 서로 교환(swap)
   i := i + 1
   j := j - 1
done

예제 코드

#include <iostream>
#include<cstring>
using namespace std;
void reverse(char s[]) {
    int len = strlen(s); //문자열의 길이를 구함
    int i, j;
    for (i = 0, j = len - 1; i < j; i++, j--) {
        swap(s[i], s[j]);
    }
}
int main() {
   char s[20] = "This is a string";
   cout << "Main String: " << s <<endl;
   reverse(s);
   cout << "Reversed String: " << s <<endl;
}

실행 결과

Main String: This is a string
Reversed String: gnirts a si sihT

위 코드에서 reverse() 함수는 strlen()으로 문자열의 길이를 구한 후, 시작 인덱스 i와 마지막 인덱스 j를 설정합니다. 그리고 i < j 조건이 유지되는 동안 swap() 함수를 호출해 양 끝의 문자를 계속 맞바꿉니다. 이 방식은 시간 복잡도가 O(n)이고 공간 복잡도가 O(1)이므로 매우 효율적입니다.