[LeetCode] 921. Minimum Add to Make Parentheses Valid

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/?envType=daily-question&envId=2024-10-09

LeetCode - Minimum Add to Make Parentheses Valid

문제 유형: 스택

문제 난이도 : Medium

 

문제

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.

 

괄호쌍 문자열은 다음의 조건이 있다:

- 빈 문자열이 가능하다.

- 두 유효한 문자열의 접합

- 유효한 문자열이 괄호로 씌여있는 형태

 

문자열 s를 받습니다. 한 번의 연산으로 문자열 내 원하는곳에 괄호를 추가할 수 있습니다.

s를 유효하게 만들기위한 최소 연산수를 구하시오.

 

풀이

스택을 이용해서 유효한 괄호들은 치운다.

만약 스택의 톱이 '('이고, 현재 읽는 문자가 ')'이라면, 스택을 pop한다.

그렇지 않으면, push한다.

 

남아있는 스택의 요소들은 짝이 없는 괄호들이다.

이 수를 반환하면 된다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minAddToMakeValid(string s) {
        stack<char> st;

        for(const auto &ch : s) {
            if(!st.empty() && st.top() == '(' && ch == ')') st.pop();
            else st.push(ch);
        }

        return st.size();
    }
};