[LeetCode] 2696. Minimum String Length After Removing Substrings

https://leetcode.com/problems/minimum-string-length-after-removing-substrings/description/?envType=daily-question&envId=2024-10-07

leetcode - Minimum String Length After Removing Substrings

문제 유형 : 스택

문제 난이도 : Easy

 

문제

You are given a string s consisting only of uppercase English letters.

You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or "CD" from s.

Return the minimum possible length of the resulting string that you can obtain.

Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.

 

영문대문자로 이루어진 문자열 s가 주어집니다.

한 번의 연산으로 s의 "AB" 또는 "CD"인 부분문자열을 삭제 할 수 있습니다.

이를 여러 번 할 수 있습니다.

제거되고 붙어진 부분도 지워질 수 있으면 지울 수 있습니다.

연산을 몇 번이고 한 뒤 최소 길이를 구하시오.

 

풀이

스택을 이용하여 제거 이후 새로 연결되는 글자들에 대해서도 연산을 적용시킬 수 있다.

스택을 만들고, 문자열을 한 번 순회하면서 다음을 반복한다:

  만약 스택이 비어있지 않고, 스택의 톱이 'A'이고 s[i]가 'B'이거나 스택의 톱이 'C'이고 s[i]가 'D'인 경우, 스택을 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 minLength(string s) {
        stack<char> st;
        int n = s.size();
        for(int i = 0; i < n; ++i) {
            if(!st.empty() && ((st.top() == 'A' && s[i] == 'B') || (st.top() == 'C' && s[i] == 'D'))) {
                st.pop();
            } else {
                st.push(s[i]);
            }
        }
        return st.size();
    }
};