C++에서 문자 배열로 저장된 문장의 단어 순서 반전하기

각 요소가 하나의 문자로 저장된 입력 문장이 주어졌을 때, 이 문장을 단어 단위로 반전시켜야 하는 상황을 생각해 보겠습니다.

예를 들어 입력이 ['t','h','e',' ','m','a','n',' ','i','s',' ','n','i','c','e'], 즉 "the man is nice"라면, 출력은 ['n','i','c','e',' ','i','s',' ','m','a','n',' ','t','h','e'], 즉 "nice is man the"가 되어야 합니다.

해결 알고리즘

이 문제는 다음 단계를 통해 해결할 수 있습니다.

1. 배열 s 전체를 반전시킵니다.
2. j := 0으로 초기화합니다.
3. n := 배열 s의 크기로 설정합니다.
4. i를 0부터 n 미만까지 1씩 증가시키며 반복합니다.
   • s[i]가 공백(' ')과 같다면
     • 인덱스 j부터 i까지의 배열 s를 반전시킵니다.
     • j := i + 1로 갱신합니다.
5. 마지막으로 인덱스 j부터 n까지의 배열 s를 반전시킵니다.

이 방법의 핵심 아이디어는 다음과 같습니다. 먼저 전체 배열을 한 번 뒤집으면 단어들의 순서는 반전되지만, 각 단어 내부의 글자들도 함께 거꾸로 됩니다. 이후 공백을 기준으로 각 단어 구간을 다시 반전시켜 주면 단어 내부의 글자 순서는 원래대로 복원되면서, 전체적으로는 단어 순서만 반전된 결과를 얻을 수 있습니다. 추가 메모리 없이 제자리(in-place)에서 처리할 수 있어 효율적입니다.

예제 코드

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   void reverseWords(vector<char>& s) {
      reverse(s.begin(), s.end());
      int j = 0;
      int n = s.size();
      for(int i = 0; i < n; i++){
         if(s[i] == ' '){
            reverse(s.begin() + j, s.begin() + i);
            j = i + 1;
         }
      }
      reverse(s.begin() + j, s.begin() + n);
   }
};
main(){
   Solution ob;
   vector<char> v = {'t','h','e',' ','m','a','n',' ','i','s',' ','n','i','c','e'};
   ob.reverseWords(v);
   print_vector(v);
}

입력

{'t','h','e',' ','m','a','n',' ','i','s',' ','n','i','c','e'}

출력

[n, i, c, e, , i, s, , m, a, n, , t, h, e]