Minimum Remove to Make Valid Parentheses

Daily 문제로 풀어봤다. 어려운 문제도 아니고 valid parentheses 문제는 stack 형식으로 많이 풀어봤지만 조금은? 다른 느낌으로 풀어봤다. 최소한의 parentheses 를 만들어야 하기 때문에 valid 가 아닌 괄호는 다 버려야 한다. 알파벳은 전부 통과 되기 때문에 알파벳은 추가 해줬지만 stack 을 확인하면서 valid 한 괄호는 표시 해두고 마지막에 valid 한 괄호만 추가 해주서 통과 됐다.

stack 문제는 많이 안풀어본 유형이여서 아직까지 좀 생각도 하게 되고 금방금방 안나와서 조금 아쉽다. Daily 라도 문제를 매일 풀어보면서 실력을 늘려보자.

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<pair<char,int>> charStack;
        string answer = "";  
        string tmp = ""; 
        for(int i = 0; i < s.length(); i++){
            if(isalpha(s[i])){
                tmp += s[i]; 
            } else if(s[i] == '('){
                charStack.push({s[i],i}); 
                tmp += '?'; 
            } else{
                if(!charStack.empty()){
                    tmp += ')';
                    tmp[charStack.top().second] = '(';  
                    charStack.pop(); 
                } else{
                    tmp += '!'; 
                }
            }
        }

        for(char& c : tmp){
            if(c != '?' && c != '!'){
                answer += c; 
            }
        }
        return answer; 
    }
};