-
99클럽 코테 스터디 16일차 TIL: 스택/큐, Leetcode 921. Minimum Add to Make Parentheses ValidToday_I_Learned/Algorithm 2024. 6. 25. 23:33
문제
https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/
통과 여부
Pass
나의 접근
- (오답) 처음에는 짝이 맞지 않는 괄호의 수를 세면 된다고 생각했다.
- (반례) 하지만 괄호의 짝은 모두 맞지만 방향이 다른 경우도 있었다. 결국 stack 을 사용하게 되었다.
- 문자열을 순회하며 '(' 는 push 하고, ')' 을 만나면 stack 에서 pop 을 하도록 한다.
- ')' 를 만났는데 stack 이 비어있으면 s 를 완성하기 위한 문자 삽입 횟수를 +1 한다.
class Solution: def minAddToMakeValid(self, s: str) -> int: ans = 0 stack = [] for c in s: if c == '(': stack.append(c) elif c == ")": if len(stack) == 0: ans += 1 else: stack.pop() return ans + len(stack)
'Today_I_Learned > Algorithm' 카테고리의 다른 글