LeetCode (C/C++) : 1249. Minimum Remove to Make Valid Parentheses

https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

---

풀이

열린 괄호와 닫힌 괄호를 관리하는 스택을 따로 두고, 괄호를 만날 때마다 저장했다.열린 괄호를 만남 - open스택에 저장닫힌 괄호를 만남 - open 스택에 값이 있다면 해당 괄호 삭제, 값이 없다면 close 스택에 저장문자열을 다 순회한 후 스택에 남아 있는 위치의 괄호들은 삭제해야 할 괄호이므로 이를 모두 동일한 문자로 만들어 준 후 문자열에서 삭제했다.

---

코드

#define DEL -1

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        int cnt = 0;
        stack <int> openLoc, closeLoc;

        for(int i = 0; i < s.size(); i++) {

            // 열린 괄호가 있다면 stack에 저장
            if (s[i] == '(') {
                cnt++;
                openLoc.push(i);
            }

            else if (s[i] == ')') {
                
                // 열린 괄호가 없다면 지워야 하는 위치이므로 stack에 저장
                if (openLoc.size() == 0)
                    closeLoc.push(i);
                
                // 있다면 해당 열린 괄호 삭제
                else
                    openLoc.pop();
            }   
        }

        // stack에 남아 있는 숫자 = 없애야 하는 괄호의 위치이므로
        // 해당 위치의 문자를 지워야 할 문자로 치환
        while (openLoc.size()) {
            s[openLoc.top()] = DEL;
            openLoc.pop();
        }
        
        while (closeLoc.size()) {
            s[closeLoc.top()] = DEL;
            closeLoc.pop();
        }
        
        // 해당 문자를 지운 후 반환
        s.erase(remove(s.begin(), s.end(), DEL), s.end());
        return s;    
    }
};