Today's Challenge

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

Remove All Adjacent Duplicates in String II - LeetCode

문제를 보고 뇌 정지가 살짝 왔다..
어찌 풀면 좋을까 고민하다가 결국엔 =_= 다른 사람이 푼 걸 봤다.

내가 제일 고민하던 건 앞에서부터 쭉 훑어 나갈 경우, 중간에 없어지는 케이스가 발생하는데
그럼 처음부터 다시 시작해야 하지 않나..? 그럼 반복을 몇 번이나 해야 하는 건가..? 였다.

근데 stack을 이용하면 매우 간단하게 풀 수 있다.
다만 내가 자주 사용하던 단순히 값만 들어 있는 stack이 아니라 [value, count] type의 스택을 쓰면 된다.
다음에는 이런 구조를 꼭 활용해보면 좋을 듯. 이런 유형을 기존에도 많이 보긴 했었다.

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        st = []
        for i in s:
            if st and st[-1][0] == i:
                st[-1][1] += 1
            else:
                st.append([i, 1])
            
            if st[-1][1] == k:
                st.pop()
        
        res = ''
        for ch, cnt in st:
            res += (ch * cnt)
        return res