[LeetCode] 1209. Remove All Adjacent Duplicates in String II

<나의 풀이>

코드없는 프로그래밍 채널의 해설을 참고해서 풀었고, 같은 문자가 k번 반복될 때마다 k번 pop을 해주는 방식으로 풀었다.

1. 문자열을 저장할 스택과 얼마나 반복됐는지 체크할 숫자스택을 만든다.

2. 문자열 스택의 마지막을 제시된 문자열과 비교해 같은지 파악한다.

3. 같으면 추가하고 숫자스택의 값도 1올려준다. => 숫자스택의 값을 체크해 k와 같으면 k만큼 pop을 해준다.

4. 같지 않으면 문자스택에 추가하고, 숫자스택에 1을 추가한다.

 

<고민했던 것>

처음에 문제를 읽고 처음 문자열 스택에서 pop을 하고 나면 변형된 스택에서 새로 겹치게 되는 것을 찾지 못하는 것이 아닌가 생각해 보니 새로 비교하는 문자를 이어서 숫자 스택에 더해주기 때문에 찾을 수 있다는 것을 알게 되었다.

st = []
        nt = []
        for c in s:
            if not st:
                st.append(c)
                nt.append(1)
            elif st[-1] == c:
                st.append(c)
                nt[-1] += 1
                
                if nt[-1] == k:
                    for _ in range(k):
                        st.pop()
                    nt.pop()
            else:
                st.append(c)
                nt.append(1)
                
        return "".join(st)

127 ms

16.1 MB

 

<다른 풀이>

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        counts = []
        cur = None
        for i in range(0, len(s)):
            if not cur:
                cur = [s[i], 1]
                continue
            if s[i] == cur[0]:
                cur[1] += 1
                if cur[1] == k:
                    cur = counts.pop() if counts else None
            else:
                counts.append(cur)
                cur = [s[i], 1]
        if cur:
            counts.append(cur)
        return "".join(
            char * count for char, count in counts
        )

111 ms

18.8 MB