[스파르타] 99클럽 2기 코테스터디 37일차 TIL / leet 921

Leetcode: 921. Minimum Add to Make Parentheses Valid (링크)

 

921. Minimum Add to Make Parentheses Valid

 

문제설명

문자열 s가 주어졌을 때 완벽히 합이 맞는 괄호 쌍이 되려면 여닫는 괄호를 몇 개 추가해야 하는지 찾는 문제이다.

간단히 말하자면 짝이 없는 괄호의 개수를 구하면 된다.

예1) 입력값: s = "())" / 출력값: (()) 여는 괄호 1개가 더 필요하므로 1 출력

예2) 입력값: s = "(((" / 출력값: ((())) 닫는 괄호 3개가 더 필요하므로 3 출력

 

풀이 설명

(1) 빈 리스트 ans를 정의한다.

(2) 입력값 s를 for문으로 하나씩 돌면서 '(' 인 경우에는 ans.append를, ')'인 경우에는 ans.pop을 해준다.

(3) 다만 일반적인 괄호쌍 문제에서는 보통 스택에 '('를 넣어두고 ')'을 만날 때마다 스택을 pop 해주는 방식인데,

여기에서는 괄호쌍이 없는 '(', ')' 둘 다 카운트해야 하므로 ')' 을 만날 때 그 이후 조건을 2가지로 나누었다.

(3-1) 바로 직전의 i가 '(' 였다면 현재 i인 ')'을 만나 괄호쌍을 만족하므로 ans.pop()을 진행한다.

(3-2) 바로 직전의 i가 ')' 였다면 괄호쌍을 만족하지 못하므로 ans.append를 진행한다.

(4) 최종적으로 ans에는 짝이 안 맞는 괄호들이 모여있으므로 ans의 길이를 리턴해주면 된다.

 

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = []
        for i in s:
            if i == '(':
                ans.append(i)
            else:
                if ans and ans[-1] == '(':
                    ans.pop()
                else:
                    ans.append(i)
        return len(ans)

오늘 미들러 풀이 끝!