LeetCode [1957]: Delete Characters to Make Fancy String

📌 LeetCode [1957]: Delete Characters to Make Fancy String

🔗 문제 링크

---

문제 설명 📄

주어진 문자열 s에서 연속된 동일한 문자가 3개 이상 나오지 않도록 문자를 삭제하여 새로운 문자열을 반환해야 합니다.

---

문제 접근 방식 📋

1. 스택 활용:
   • 문자열을 순회하며 각 문자를 스택에 추가합니다.
   • 스택의 길이가 3 이상일 때, 마지막 세 문자가 동일하면 가장 마지막 문자를 제거합니다.
   • 이를 반복하면서 조건에 맞는 결과 문자열을 생성합니다.
2. 시간 복잡도 최적화:
   • 스택을 사용하여 O(n) 시간 복잡도로 해결할 수 있습니다.

---

Solution 💻

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

        for i in s:
            stack.append(i)
            if len(stack) > 2:
                if stack[-1] == stack[-2] and stack[-2] == stack[-3]:
                    stack.pop()

        return "".join(stack)

---

시간 복잡도 분석 ⏲️

• 문자열 순회: O(n) – 문자열의 각 문자를 한 번씩 순회합니다.
• 스택 연산: O(1) – 스택에 문자 추가 및 제거는 상수 시간에 수행됩니다.
• 결과 문자열 생성: O(n) – 리스트를 문자열로 변환하는 비용입니다.
• 총 시간 복잡도: O(n)

공간 복잡도 분석 🗄️

• 스택 공간: O(n) – 결과를 저장하는 스택의 최대 크기.
• 추가 변수: O(1) – 다른 변수는 사용되지 않습니다.

---

리팩토링 🛠️

개선된 코드

class Solution:
    def makeFancyString(self, s: str) -> str:
        result = []
        count = 1

        result.append(s[0])

        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                count += 1
            else:
                count = 1

            if count < 3:
                result.append(s[i])

        return "".join(result)

리팩토링 후 시간 복잡도 ⏲️

• 문자열 순회: O(n) – 기존과 동일하지만 조건 검사를 더 단순화했습니다.
• 총 시간 복잡도: O(n)

리팩토링 후 공간 복잡도 🗄️

• 결과 리스트: O(n)
• 추가 변수: O(1) – 카운터 변수만 사용.

---