99클럽 코테 스터디 28일차 TIL [LeetCode] Minimum Add to Make Parentheses Valid (Java)

📃 문제

[LeetCode] Minimum Add to Make Parentheses Valid

🖋️ 풀이

완성형 괄호를 만들기 위해 추가해야 하는 괄호의 최소 갯수를 구하는 문제

• 필요한 괄호의 최소 갯수는 answer에 저장해 반환한다.
• 주어진 문자열 s의 각 문자를 탐색한다.
• 문자가 열린 괄호(()라면, 스택에 추가한다.
• 닫힌 괄호())를 만난 경우
  • 스택이 비어있지 않다면, 완전한 괄호를 만들 수 있으므로 pop() 실행
  • 스택이 비어있다면, 닫힌 괄호의 짝이 필요한 것이므로 answer 증가
• for문 종료 후, 스택에 남은 열린 괄호는 짝이 필요한 것이므로 answer에 추가한다.

✅ 정답 코드

class Solution {
    public int minAddToMakeValid(String s) {
        int answer = 0;
        Stack<Character> st = new Stack<>();
        for(char c : s.toCharArray()) {
            if(c == '(') {
                st.add('(');
            } else {
                if(st.isEmpty()) {
                    answer++;
                } else {
                    st.pop();
                }
            }
        }
        answer += st.size();
        return answer;
    }
}

🔍 다른 풀이

스택을 사용하지 않아 메모리 효율을 높일 수 있다.

• 스택에 열린 괄호를 저장하는 대신 cnt를 증가시키고, pop() 대신 cnt를 감소시킨다.

class Solution {
    public int minAddToMakeValid(String s) {
        int cnt = 0;
        int answer = 0;

        for(char c : s.toCharArray()) {
            if(c == '(') {
                cnt++;
            } else {
                if(cnt > 0) {
                    cnt--;
                } else {
                    answer++;
                }
            }
        }

        answer += cnt;

        return answer;
    }
}