921-kir3i.md

921. Minimum Add to Make Parentheses Valid

Solution

• 시간복잡도: O(N)

• 알고리즘

  구현, 스택

• 풀이설명

  1. 주어진 문자열 S를 스캔하면서 (가 있을 땐 스택에 담습니다.
  2. )가 있을 땐 스택의 top을 확인하여 (가 있을 때 pop을 수행하고 top이 (가 아니라면 )를 스택에 담습니다.
  3. 스캔이 모두 끝난 뒤, 스택의 크기가 곧 답이 됩니다.

  혹은 그냥 스택을 사용하지 않고 여태까지 나온 괄호 중 짝이 맞지 않는 괄호들을 세주는 것만으로도 답을 구할 수 있습니다.

• 소스코드

  • C++

    class Solution {
    public:
        stack<char> s;
        int minAddToMakeValid(string S) {
            for(const char &c: S) {
                if(c=='(')
                    s.push(c);
                else if(c==')') {
                    if(!s.empty() && s.top() == '(')
                        s.pop();
                    else
                        s.push(')');
                }
            }
            return s.size();
        }
    };

  • Python

    class Solution:
        def minAddToMakeValid(self, S):
            openCnt = 0
            closeCnt = 0
            for c in S:
                if c == '(':
                    openCnt += 1
                elif c == ')':
                    if openCnt > 0:
                        openCnt -= 1
                    else:
                        closeCnt += 1
            return openCnt+closeCnt

  • Java

    class Solution {
        public int openCnt = 0;
        public int closeCnt = 0;
        public int minAddToMakeValid(String S) {
            for(int i=0; i<S.length(); i++) {
                if (S.charAt(i) == '(')
                    openCnt++;
                else if(S.charAt(i) == ')') {
                    if (openCnt > 0)
                        openCnt--;
                    else
                        closeCnt++;
                }
            }
            return openCnt + closeCnt;
        }
    }