입력으로 주어진 문자열(문자 배열)을 받아, 각 단어 내부의 글자 순서는 그대로 유지하면서 단어와 단어의 위치만 서로 뒤바꾸는 문제입니다.
예를 들어 입력이 ['t','h','e',' ','m','a','n',' ','i','s',' ','n','i','c','e']라면, 출력은 ['n','i','c','e',' ','i','s',' ','m','a','n',' ','t','h','e']가 됩니다. 즉, "the man is nice"라는 문장이 "nice is man the"로 변환됩니다.
해결 접근 방법
이 문제는 두 단계 반전(two-pass reversal) 기법으로 효율적으로 해결할 수 있습니다. 알고리즘은 다음과 같습니다.
- 배열 s 전체를 반전시킵니다.
- j := 0으로 초기화합니다.
- n := 배열 s의 크기로 설정합니다.
- i를 0부터 n 미만까지 1씩 증가시키며 반복합니다.
- s[i]가 공백(' ')과 같다면:
- 인덱스 j부터 i 직전까지의 구간을 반전시킵니다.
- j := i + 1로 갱신합니다.
- s[i]가 공백(' ')과 같다면:
- 마지막으로 인덱스 j부터 n까지의 구간을 반전시킵니다.
동작 원리
전체 문자열을 먼저 뒤집으면 단어들도 함께 거꾸로 됩니다. 이후 공백을 기준으로 각 단어 구간만 다시 한 번 뒤집으면, 단어 내부의 글자 순서는 원래대로 돌아오고 단어들의 배치만 반전된 상태가 됩니다. 예를 들어 "the man is nice"를 전체 반전하면 "ecin si nam eht"가 되고, 여기서 각 단어("ecin", "si", "nam", "eht")를 개별적으로 반전하면 "nice is man the"가 완성됩니다.
이 방법은 추가 메모리 없이 제자리(in-place)에서 수행되며, 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.
구현 예제
다음 C++ 코드를 통해 더 쉽게 이해할 수 있습니다.
#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]
출력 결과에서 공백 문자는 화면에 빈 값으로 표시됩니다. 실제 배열에는 공백(' ')이 그대로 유지되어 있으며, 결과적으로 "nice is man the"라는 문장 형태로 단어 순서가 반전된 것을 확인할 수 있습니다.