C++ ] leetCode 1249 - Minimum Remove to Make Valid Parentheses

 

 

리트코드 1249번 문제

 

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

 

Example 1:

• Input: s = "lee(t(c)o)de)"
• Output: "lee(t(c)o)de"
• Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

 

Example 2:

• Input: s = "a)b(c)d"
• Output: "ab(c)d"

 

 

Example 3:

• Input: s = "))(("
• Output: ""
• Explanation: An empty string is also valid.

 

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either'(' , ')', or lowercase English letter.

 

 

문자열을 순회하면서 stack을 사용하여 등장한 괄호가 '(' 이고 stack의 top에 있는 인덱스 괄호가 ')' 인 경우에는 올바른 괄호를 구성하고 있으니 stack에서 pop하면서 stack에는 올바르지 않은 괄호의 인덱스만 남겨둘 수 있다.

 

그 다음 stack에 들어있지 않은 인덱스만 ans 문자열에 추가하면서 정답 문자열을 reverse 버전을 구성하고 마지막으로 뒤집는 방법을 택했다.

 

이렇게 한 이유는 ans = s[i] + ans;를 하면 memory limit exceeded 되기 때문이다.

 

std::string에서 s += str[i];와 s = s + str[i];는 같은 동작을 수행하는 것처럼 보이지만 내부적인 처리와 메모리 사용 측면에서 차이가 있다. s += str[i]; 연산은 현재 문자열 s에 str[i]를 직접 추가하는 반면 s = s + str[i]; 연산은 s와 str[i]를 결합한 새로운 문자열을 만들고, 그 결과를 s에 복사하므로 이 과정에서 새로운 문자열 객체가 임시로 생성되기 때문에 메모리 사용량이 불필요하게 많아지고 실행 시간도 더 길어질 수 있다.

 

 

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        int len = s.length();
        stack<int> st;
        vector<int> idx;
        string ans = "";

        for(int i = 0; i < len; i++) {
            if(s[i] == '(') {
                st.push(i);
            }
            else if(s[i] == ')') {
                if(!st.empty() && s[st.top()] == '(') {
                    st.pop();                    
                }
                else {
                    st.push(i);
                }
            }
        }

        for(int i = len - 1; i >= 0; i--) {
            if(!st.empty() && st.top() == i) {
                st.pop();
            }
            else {
                ans += s[i];
            }
        }
        
        reverse(ans.begin(), ans.end());

        return ans;
    }
};