1190 Reverse Substrings Between Each Pair of Parentheses

1190. Reverse Substrings Between Each Pair of Parentheses / c++ / Medium / 5분

문제 및 코드

문제 링크

#include <stack>
using namespace std;
class Solution {
public:
    string reverseParentheses(string s) {
        string currentString = "";
        stack<string> Stack;
        for (int i = 0; i < s.length(); ++i)
        {
            if (s[i] == '(')
            {
                Stack.push(currentString);
                currentString = "";
            }
            else if (s[i] == ')')
            {
                reverse(currentString.begin(), currentString.end());
                currentString = Stack.top() + currentString;

                Stack.pop();
            }
            else
            {
                currentString += s[i];
            }
        }

        return currentString;
    }
};

접근 방식

문자열 / 자료 구조 / 스택

1. 전형적인 괄호 문제 + 문자열 뒤집기가 섞여 있는 문제였다.
2. 하지만 문자를 하나씩 스택에 넣고 다시 꺼내서 그걸 뒤집게 되면 시간 효율이 떨어질 것이라고 판단했다.
3. 그래서 문자열을 괄호 상황에 따라서 스택에 넣어다 꺼내는 방식으로 구상해봤다.
4. 문자열 s를 순회하면서 아래의 로직을 수행한다.
   1. 현재 문자가 ‘(‘ 라면, 현재 문자열을 스택에 집어넣고, 현재 문자열을 초기화 한다.
   2. 현재 문자가 ‘)’ 라면, 현재 문자열을 뒤집은 뒤, 스택의 가장 위의 문자열을 꺼내서 현재 문자열 앞에 붙인다.
5. 현재 문자열을 반환
6. 해결

생각해 볼 점

1. 이전까지는 괄호 문제를 풀 때, 스택에 하나씩 넣고 빼는 방식을 주로 사용했었다.
2. 이번엔 문자열을 뒤집는 방식이 추가되어, 스택의 입출력에 과부하가 걸릴 것이라고 생각하여 문자 대신 문자열을 이용하는 방식으로 수정해서 작성해봤는데, 원하던데로 잘 작동하여 성취감을 느낄 수 있었다.