Leetcode 921 Minimum Add to Make Parentheses Valid (Java)

class Solution {
    public int minAddToMakeValid(String s) {
        
    
        Stack<Character> st=new Stack();

        int cnt2=0;

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

            

            if(st.empty()){
                if(s.charAt(i)=='('){
                    st.push(s.charAt(i));
                }else{
                    cnt2++;
                }
            }
            else{
                if(s.charAt(i)=='('){
                    st.push(s.charAt(i));
                }else{
                    st.pop();
                }
            }
        }


        return st.size()+cnt2;


    }
}

1. 문제

2. 풀이

빈 문자열을 포함해 여는 괄호만큼 다음에 닫는 괄호가 나오면 해당 문자열은 valid하다. 괄호로 이루어진 문자열이 주어졌을 때, 이를 valid한 괄호로 만들 최소 문자의 수를 구하는 문제이다. 스택으로 풀 수 있다.

        Stack<Character> st=new Stack();

        int cnt2=0;

        for(int i=0;i<s.length();i++){        
            if(st.empty()){
                if(s.charAt(i)=='('){
                    st.push(s.charAt(i));
                }else{
                    cnt2++;
                }
            }
            
            ..

 괄호를 여는 문자열을 넣을 스택과 남는 닫는 괄호의 수를 저장할 변수를 선언해준다. 닫는 괄호 다음 여는 괄호가 나올 수 있으므로 따로 계산해주어야 한다.

 해당 괄호가 여는 괄호라면 스택에, 닫는 괄호라면 변수에 추가해준다.

            else{
                if(s.charAt(i)=='('){
                    st.push(s.charAt(i));
                }else{
                    st.pop();
                }
            }

스택에는 여는 괄호가 들어있는 상태이다. 여는 괄호가 들어오면 스택에 넣고, 닫는 괄호가 들어오면 스택의 여는 괄호와 상쇄되므로 pop한다.

        return st.size()+cnt2;

연산이 끝나고 여는 괄호는 문자열의 오른쪽에 닫는 괄호를 넣고, 남는 닫는 괄호는 문자열의 왼쪽에 여는 괄호를 각각 해당 갯수만큼 넣어주면 정답을 구할 수 있다.