[LeetCode] 1963. Minimum Number of Swaps to Make the String Balanced

https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/description/?envType=daily-question&envId=2024-10-08

leetcode - Minimum Number of Swaps to Make the String Balanced

문제 유형: 스택

문제 난이도 : Medium

 

문제

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

• It is the empty string, or
• It can be written as AB, where both A and B are balanced strings, or
• It can be written as [C], where C is a balanced string.

You may swap the brackets at any two indices any number of times.

Return the minimum number of swaps to make s balanced.

 

문자열 s가 짝수길이 n으로 주어집니다.

문자열은 정확하게  n/2개의 '['와 ']'가 각각 있습니다.

빈 문자열이거나, 괄호쌍이 맞으면 균형이 잡혀있는 모습입니다.

 

s를 균형있게 하기위한 최소 swap 횟수를 구하시오.

 

풀이

스택을 만들어서 괄호쌍을 저장한다.

'['를 만나면 스택에 담는다.

']'인 경우, 스택이 비어있다면 담는다.

그게 아니고 스택의 톱이 '['이라면, 스택을 하나 pop시킨다.

 

스택의 최종 크기에는 매칭되지 않은 괄호쌍들이 있다.

이 크기에 /2를 해주면 된다.

 

코드

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 minSwaps(string s) {
        stack<char> stk;

        for(int i = 0; i < s.size(); ++i) {
            if(stk.empty() || s[i] == '[') stk.push(s[i]);
            else if(stk.top() == '[') stk.pop();
        }
        return stk.size()/2;
    }
};