[LeetCode] 1190. Reverse Substrings Between Each Pair of Parentheses

https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/description/

leetcode - Reverse Substrings Between Each Pair of Parentheses

문제 유형 : 스택

문제 난이도 : Medium

 

문제

You are given a string s that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any brackets.

괄호와 영문자로 구성된 문자열 s를 입력받는다.

맨 안쪽 괄호쌍의 안부터 뒤집는 연산을 하여라.

연산 후 괄호는 없애라.

 

풀이

스택에 괄호쌍을 여는 곳의 인덱스를 저장한다.

문자열을 순차적으로 순회하면서, 괄호를 여는 인덱스를 저장하고, 괄호를 닫아주는 문자를 발견하면 스택에서 인덱스를 pop하여 그 pop된 인덱스부터 현재 인덱스까지 뒤집는다.

이제 s는 괄호가 포함된 뒤집힌 문자열이 되는데, 괄호만 제거해서 반환하면 된다.

 

 

코드

C++

class Solution {
public:
    string reverseParentheses(string s) {
        stack<int> st;
        int n = s.size();
        for(int i = 0; i < n; i++) {
            if(s[i] == '(') {
                st.push(i);
            } else if(s[i] == ')') {
                int j = st.top();
                st.pop();
                reverse(s.begin() + j + 1, s.begin() + i);
            }
        }

        string res = "";
        for(const auto &ch : s) {
            if(ch != '(' && ch != ')') {
                res += ch;
            }
        }

        return res;
    }
};