LeetCode [1047]: Remove All Adjacent Duplicates In String

📌 LeetCode [1047]: Remove All Adjacent Duplicates In String

🔗 문제 링크

---

문제 설명 📄

문자열 s가 주어졌을 때, 인접한 중복 문자 쌍을 제거하는 문제입니다.
중복 문자 제거는 반복적으로 수행되며, 더 이상 제거할 수 없을 때 최종 문자열을 반환합니다.

---

문제 접근 방식 📋

1. 스택 활용:
   • 스택을 사용하여 문자열의 문자를 순회하며 인접한 문자가 중복되는 경우 제거.
   • 스택의 마지막 문자가 현재 문자와 같다면 스택에서 제거.
   • 그렇지 않다면 스택에 현재 문자를 추가.
2. 결과 반환:
   • 최종 스택에 남아 있는 문자를 이어 붙여 결과 반환.

---

Solution 💻

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []

        for i in s:
            if stack and stack[-1] == i:
                stack.pop()
            else:
                stack.append(i)

        return "".join(stack)

시간 복잡도 ⏲️

• 문자 순회: (O(n)), (n)은 문자열의 길이.
• 스택 연산: 각 문자에 대해 한 번씩 추가/제거: (O(n)).
• 최종 시간 복잡도: (O(n)).

공간 복잡도 🗄️

• 스택 공간: (O(n)), 최악의 경우 모든 문자가 스택에 추가될 수 있음.
• 총 공간 복잡도: (O(n)).

---