921. Minimum Add to Make Parentheses Valid (String, Stack, Greedy)

링크 - https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

이 문제는 stack으로 풀어도 되나, 최적의 공간효율도를 위해 상수 변수로 풀 수 있다. (가 나오면 num_open_brackets을 1 더하고, )가 나왔는데 num_open_brackets > 0 이면 1 빼는 식으로 하면 된다. 만약에 num_open_brackets <= 0인데 )가 나오면, 우리는 (를 나중에 더해줘야하므로 ans에 1을 더해준다. 마지막에 ans와 num_open_brackets을 더한 값을 반환한다.

Code

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        if not s:
            return True

        ans = 0
        num_open_brackets = 0
        for c in s:
            if c == "(":
                num_open_brackets += 1
            else:
                if num_open_brackets > 0:
                    num_open_brackets -= 1
                else:
                    ans += 1

        return ans + num_open_brackets

Complexity

Time Complexity: O(n) s를 for문으로 도므로 s의 길이인 n만큼 시간 소요

Space Complexity: O(1) 상수 변수만 사용