C++로 문자열의 단어 순서 뒤집기: 단계별 알고리즘과 코드 예제

문제 개요

여러 개의 단어로 구성된 문자열이 있다고 가정해 보겠습니다. 이때 문자열 안에서 단어들의 위치를 서로 반대로 뒤집어야 합니다. 예를 들어 입력 문자열이 "The quick brown fox jumps over a lazy dog"라면, 처리 결과는 "dog lazy a over jumps fox brown quick The"가 되어야 합니다.

단순히 순서만 바꾸는 것 외에도, 실제 구현에서는 다음 조건들을 함께 처리해야 깔끔한 결과를 얻을 수 있습니다.

문자열 맨 앞과 맨 뒤에 있는 공백은 모두 제거합니다.
단어 사이에 공백이 여러 개 연속으로 있으면 하나의 공백으로 줄입니다.
각 단어 내부의 글자 순서는 원래 그대로 유지합니다.

해결 접근 방식

가장 효율적인 방법은 "전체 반전 → 단어별 반전"이라는 두 단계 기법입니다. 문자열 전체를 먼저 뒤집으면 단어들의 순서는 바뀌지만 각 단어의 글자들은 거꾸로 되어 있습니다. 이 상태에서 각 단어를 다시 한 번 뒤집어 주면, 단어 순서는 반전된 채 글자 순서만 정상적으로 복원됩니다.

이제 구체적인 알고리즘 단계를 살펴보겠습니다.

1단계: getString() 함수 정의

입력 문자열 s를 받아 양 끝의 공백을 제거하고, 중간의 연속된 공백을 하나로 정리한 결과를 반환하는 함수입니다.

i := 0, j := (s의 길이 − 1)로 초기화합니다.
s[i]가 공백인 동안 i를 1씩 증가시켜 앞쪽 공백을 건너뜁니다.
j가 0 이상이고 s[j]가 공백인 동안 j를 1씩 감소시켜 뒤쪽 공백을 건너뜁니다.
빈 문자열 ret을 선언합니다.
i부터 j까지 순회하면서 다음을 수행합니다.
- ret이 비어 있지 않고, ret의 마지막 문자가 공백이며, 현재 s[i]도 공백이라면 이번 반복은 건너뜁니다(연속 공백 방지).
- 그렇지 않으면 ret에 s[i]를 추가합니다.

2단계: reverseWords() 함수 정의

반전된 문자열에서 각 단어의 시작 위치와 끝 위치를 찾아, 해당 단어만 다시 뒤집는 함수입니다.

j := 0으로 초기화합니다.
i를 0부터 s의 길이 − 1까지 진행하되, 매 반복마다 i := j로 설정합니다.
- s[i]가 공백이면 j := i + 1로 설정하고 다음으로 넘어갑니다.
- 공백이 아니라면:
  - j + 1이 s의 길이보다 작고 s[j + 1]이 공백이 아닌 동안 j를 증가시켜 단어의 끝을 찾습니다.
  - x := i, y := j로 설정한 뒤, x < y인 동안 s[x]와 s[y]를 교환하고 x는 증가, y는 감소시켜 해당 단어를 뒤집습니다.
  - j를 1 증가시킵니다.

3단계: 메인 로직

문자열 s 전체를 반전합니다.
reverseWords(s)를 호출하여 각 단어를 다시 반전합니다.
getString(s)를 호출하여 공백을 정리한 최종 결과를 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        reverseWordss(s);
        return getString(s);
    }
    string getString(string s){
        int i = 0;
        int j = s.size() - 1;
        while(s[i] == ' ' && i < s.size()) i++;
        while(j >= 0 && s[j] == ' ') j--;
        string ret = "";
        for(;i <= j; i++){
            if(ret.size() && ret.back() == ' ' && s[i] == ' ')continue;
            ret += s[i];
        }
        return ret;
    }
    void reverseWordss(string& s){
        int j = 0;
        for(int i = 0; i < s.size() ;i = j){
            if(s[i] == ' '){
                j = i + 1;
            }
            else{
                while(j + 1 < s.size() && s[j + 1] != ' ') j++;
                int x = i;
                int y = j;
                while(x < y){
                    swap(s[x], s[y]);
                    x++;
                    y--;
                }
                j++;
            }
        }  
    }
};
main(){
    Solution ob;
    cout << (ob.reverseWords("The quick brown fox jumps over a lazy dog"));
}

실행 결과 확인

입력

"The quick brown fox jumps over a lazy dog"

출력

"dog lazy a over jumps fox brown quick The"

마무리

이 알고리즘은 문자열을 세 번 순회하므로 시간 복잡도는 O(n)이며, 출력용 문자열을 제외하면 제자리(in-place) 방식으로 동작합니다. "전체 반전 후 부분 반전"이라는 우아한 아이디어 덕분에 코드가 간결하면서도 효율적입니다. 코딩 인터뷰에서 자주 등장하는 대표적인 문자열 조작 문제이므로, 위 풀이 과정을 직접 구현해 보며 익혀두면 큰 도움이 될 것입니다.