99클럽 코테 스터디 37일차 TIL + 스택/큐(Minimum Add to Make Parentheses Valid)

오늘의 과제

리트코드 medium으로 분류된 Minimum Add to Make Parentheses Valid 입니다.

 

이번 유형은 스택/큐 입니다.

문제

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

 

 

먼저 문제 요구사항 요약입니다.

 

짝이 맞거나 맞지 않은 괄호가 주어질 때 삽입이나 이동을 통해 온전한 괄호를 만들 수 있는 최소 이동 횟수를 반환하면 됩니다.

 

문제의 분류가 스택이고 스택 단골 문제인 괄호가 나왔으니 스무스하게 풀어주면 됩니다. 스택 기초 문제로는 짝이 맞는 문자열이라면 true, 맞지 않는다면 false를 반환하는 문제에서 조~금 심화 문제인데 기존의 공식과 똑같이 진행하면 됩니다.

 

먼저 (를 만난다면 스택에 넣어주고, )를 만났을 때 스택의 이전 값이 (라면 짝이 맞으니 카운트 할 필요가 없습니다. 따라서 pop을 통해 제거해주고, 짝이 맞지 않는다면 해당 괄호는 움직이거나 값의 삽입을 통해 맞춰줘야 하니 카운트를 해줍니다. 

 

또한, 문자열을 모두 순회하고도 스택에 값이 남아있다면 그 문자들 역시 이동하거나 값의 삽입을 통해 짝을 찾아주어야 하니 스택의 사이즈만큼 카운트해줍니다.

 

 

코드입니다.

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

        for (char c : s.toCharArray()) {
            if (c == '(') {
                st.push(c);
            }else {
                if(!st.isEmpty() && st.peek() == '(') {
                    st.pop();
                } else {
                    answer++;
                }
            }
        }
        answer += st.size();
        return answer;
    }
}

 

 

 

 

오늘의 한줄평

인생은 습관이 전부다.