C++로 배열과 문자열 뒤집기: 반복문과 재귀 두 가지 방법 완벽 정리

이 글에서는 주어진 배열 또는 문자열의 요소들을 역순으로 뒤집는 C++ 프로그램을 만들어 보겠습니다. 배열과 문자열 모두 동일한 원리로 처리할 수 있습니다.

문제 이해하기

먼저 예시를 통해 문제를 살펴보겠습니다.

입력

array = {2, 5, 7, 1, 9}

출력

{9, 1, 7, 5, 2}

입력

string = "Hello!"

출력

!olleH

알고리즘 접근 방식

프로그램을 만들기 위해서는 배열이나 문자열의 요소를 순회하면서 처리하면 됩니다. 핵심 아이디어는 다음과 같습니다.

두 개의 포인터(인덱스)를 활용하는 방식입니다. 하나는 시작(start) 위치를 가리키고, 다른 하나는 끝(end) 위치를 가리킵니다. 두 위치의 요소를 서로 교환(swap)한 후, start 값은 1씩 증가시키고 end 값은 1씩 감소시킵니다. 이 과정은 start가 end보다 작은 동안 계속되며, 두 포인터가 중간에서 만나거나 교차하면 뒤집기가 완료됩니다.

이러한 로직은 반복문(iterative) 방식과 재귀(recursive) 방식, 두 가지 방법으로 구현할 수 있습니다. 아래에서 두 방법 모두의 동작 과정을 코드와 함께 살펴보겠습니다.

방법 1: 반복문(Iterative) 활용

while 루프를 사용하여 start와 end가 교차할 때까지 요소를 교환하는 방식입니다.

#include <iostream>
using namespace std;

void reverseArrayIt(int arr[], int start, int end){
    while (start < end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

int main() {
    int arr[] = {6, 9, 1, 4, 0, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"원본 배열 : ";
    for (int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    reverseArrayIt(arr, 0, n-1);
    cout << "뒤집힌 배열 : ";
    for (int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

실행 결과

원본 배열 : 6 9 1 4 0 5
뒤집힌 배열 : 5 0 4 1 9 6

방법 2: 재귀(Recursive) 활용

재귀 방식은 함수 내부에서 자기 자신을 호출하며, start와 end 인덱스를 각각 증가·감소시켜가며 요소를 교환합니다. start가 end보다 크거나 같아지면 재귀 호출을 종료하는 것이 기저 조건(base case)입니다.

#include <iostream>
using namespace std;

void reverseArrayRec(int arr[], int start, int end){
    if(start >= end)
        return;
    int temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    reverseArrayRec(arr, start+1, end-1);
}

int main() {
    int arr[] = {6, 9, 1, 4, 0, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"원본 배열 : ";
    for (int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    reverseArrayRec(arr, 0, n-1);
    cout << "뒤집힌 배열 : ";
    for (int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

실행 결과

원본 배열 : 6 9 1 4 0 5
뒤집힌 배열 : 5 0 4 1 9 6

마무리

두 방법 모두 시간 복잡도는 O(n)으로 동일하지만, 반복문 방식은 추가 메모리 없이 안정적으로 동작하는 반면, 재귀 방식은 호출마다 스택 메모리를 사용하므로 배열이 매우 클 경우 스택 오버플로우에 유의해야 합니다. 일반적인 상황에서는 반복문 방식이 더 효율적이며, 재귀 방식은 알고리즘 학습 및 분할 정복 사고방식을 익히는 데 유용합니다.