[코테] 99클럽 코테 스터디 37일차 TIL - 스택/큐

Question1 - [미들러] 최소 추가로 유효한 괄호 만들기 (Minimum Add to Make Parentheses Valid)

 

문제 설명 https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/

 

A parentheses string is valid if and only if:

• It is the empty string,
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.
• You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

 

Example 1:

• Input: s = "())"
• Output: 1

Example 2:

• Input: s = "((("
• Output: 3

Constraints:

• 1 <= s.length <= 1000
• s[i] is either '(' or ')'

---

 

문제풀이

 

trial1

 

기존의 스택/큐 괄호 문제는 주어진 string이 valid한 괄호인지 여부 ()가 서로 닫혀있는 형태로 이루어져있는지 여부를 판별했었다.

이전에 풀었던 괄호 기본 문제는 아래를 참고.

https://ysryuu.tistory.com/70

[코테] 99클럽 코테 스터디 4일차 TIL - 스택/큐

 

이 문제의 경우는 valid여부를 검사할 뿐아니라 valid하지 않을 경우, valid하기 위해서 몇개의 괄호를 추가해야 하는지 알아내야 한다.

 

최소한의 추가될 괄호 개수를 구하기 위해 스택 두개를 만들었다.

하나의 스택에는 사라지지 않은 '('괄호를, 다른 하나의 스택에는 사라지지 않은 ')'를 넣었다. 

• 스택 2개 생성 
• string에서 '('가 발견되면, stack1에 추가한다 (열린 괄호이므로) 
• string에서 ')'가 발견되면, stack1의 마지막 괄호가 '('일 경우, 마지막 괄호를 pop으로 제거해준다. (() 의 valid 쌍이 생긴 것이므로) 
• 그러나 stack1이 비어있거나, 마지막 괄호가 '('이 아닐 경우, stack2에 ')'를 추가해준다 
• 결과적으로 stack1에는 쌍을 이루지 못한 '('가 남아있게 되고, stack 2에는 쌍을 이루지 못한 ')'만 남아있게 된다.
• 즉, 각각의 stack1, stack2에 있는 괄호들의 개수만큼 상대 괄호를 추가해 전체 string을 valid하게 만들어주어야 한다.
• 이에 따라 최소한의 추가 괄호 개수는 len(stack1) + len(stack2)와 같게 된다.

class Solution(object):
    def minAddToMakeValid(self, s):
        
        stack1 = []
        stack2 = []
        for i in s : 
            if i == '(':
                stack1.append(i)
            else : 
                if stack1 and stack1[-1] == '(':
                    stack1.pop()
                else : 
                    stack2.append(i)

        return len(stack1) + len(stack2)