소문자 알파벳과 괄호로 구성된 문자열 s가 주어졌다고 가정해 봅시다. 우리가 해야 할 작업은 가장 안쪽 괄호부터 시작하여 서로 짝을 이루는 각 괄호 쌍 내부의 문자열을 뒤집는 것이며, 최종 결과에는 괄호가 남아 있으면 안 됩니다.
예를 들어 입력이 "(hel(lowo)rld)"라고 한다면, 출력은 "dlrlowoleh"가 됩니다. 변환 과정은 다음과 같이 진행됩니다.
"(hel(lowo)rld)" → "(helowolrld)" → "dlrowoleh"
해결 접근 방법
이 문제는 스택(Stack)을 활용한 방향 전환 기법으로 효율적으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- n := 문자열의 길이로 설정하고, 길이가 n인 배열 par를 생성한 뒤 스택 st를 정의합니다.
- i를 0부터 n-1까지 순회하면서 다음을 수행합니다.
- s[i]가 여는 괄호 '('라면 해당 인덱스 i를 스택 st에 push 합니다.
- s[i]가 닫는 괄호 ')'라면 스택에서 인덱스를 pop 하여 j에 저장하고, par[i] := j, par[j] := i로 설정하여 괄호 쌍의 위치를 서로 매핑합니다.
- 빈 문자열 ret을 정의합니다.
- i := 0, d := 1로 초기화한 후, i < n 조건을 만족하는 동안 i를 d만큼씩 이동시키며 순회합니다.
- s[i]가 여는 괄호나 닫는 괄호라면 i := par[i]로 점프하고, d := -d로 방향을 반대로 바꿉니다.
- 그렇지 않으면 ret에 s[i]를 추가합니다.
- 모든 순회가 끝나면 ret을 반환합니다.
이 방식의 핵심 아이디어는 괄호를 만날 때마다 미리 계산해 둔 짝 위치로 '텔레포트'하면서 이동 방향을 뒤집는 것입니다. 이렇게 하면 실제로 문자열을 반복해서 뒤집지 않고도 한 번의 선형 순회로 최종 결과를 얻을 수 있어 시간 복잡도는 O(n)입니다.
C++ 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void out(vector <int>& v){
for(int i = 0; i < v.size(); i++){
cout << v[i] << " " ;
}
cout << endl;
}
string reverseParentheses(string s) {
int n = s.size();
vector <int> par(n);
stack <int> st;
for(int i = 0; i < n; i++){
if(s[i] == '('){
st.push(i);
}
else if(s[i] == ')'){
int j = st.top();
st.pop();
par[i] = j;
par[j] = i;
}
}
string ret = "";
for(int i = 0, d = 1; i < n; i += d){
if(s[i] == '(' || s[i] == ')'){
i = par[i];
d = -d;
}
else{
ret += s[i];
}
}
out(par);
return ret;
}
};
main(){
Solution ob;
cout << (ob.reverseParentheses("(hel(lowo)rld)"));
}입력
"(hel(lowo)rld)"
출력
13 0 0 0 9 0 0 0 0 4 0 0 0 0 dlrlowoleh
출력 결과를 보면 배열 par에는 각 괄호 쌍의 인덱스가 서로 교차하여 저장되어 있으며, 최종적으로 괄호가 모두 제거되고 내부 문자열이 반전된 "dlrlowoleh"가 반환된 것을 확인할 수 있습니다.