2696. Minimum String Length After Removing Substrings

Problem : https://leetcode.com/problems/minimum-string-length-after-removing-substrings

 

Difficulty : Easy

 

Status : Solved

 

Time : 00:03:54

 

---

 

문제 설명

 

 

대문자 알파뱃으로만 이루어진 문자열 s를 입력으로 받는다.

 

이 문자열에 어떤 동작을 시행할 수 있는데, 한 동작에서 s 내의 "AB" 혹은 "CD"로 등장하는 부분문자열을 지울 수 있다.

 

이 동작으로 얻을 수 있는 가능한 가장 작은 문자열의 길이를 구하여라.

 

부분문자열을 지운 후에 새로운 "AB" 혹은 "CD" 문자열이 생성될 수 있음을 명심하라.

---

 

풀이

 

그리디하게, 스택을 사용하면 쉽게 풀 수 있다.

스택에 문자열의 문자들을 저장하되, 현재 문자와 스택의 맨 앞의 문자가 "AB", "CD"기만 하면 서로 삭제해준다. 만약 둘 모두 해당되지 않으면 그대로 스택에 저장한다. 마지막에는 스택의 길이를 제거하면 된다.

 

AB, CD가 겹치지 않는 부분문자열이고, 계속해서 AB와 CD를 어떤 순서로 제거하던 결국은 최적의 해로 이어지기 때문에 그리디를 사용해 볼 수 있겠다.

 

풀이 코드

class Solution:
    def minLength(self, s: str) -> int:
        stack = []
        for _s in s :
            if stack and (stack[-1] == 'A' and _s == 'B' or stack[-1] == 'C' and _s == 'D') :
                    stack.pop()
                    continue
            stack.append(_s)
        return len(stack)

풀이 완료!