[LeetCode] 3174. Clear Digits (Python)

Problem

 

Solution

string, stack

문자열 s에서 digit이 있으면 digit 과 그 왼쪽에있는 문자를 제거하는 문제 (반복).

문자열을 순회하면서 해당 index를 기준으로 digit 여부와 왼쪽 문자를 체크하여 s 를 업데이트한 후 조건에 해당되지 않을 때까지 반복한다.

 

<다른 코드>

다른 코드에서는 alpha이면 list에 저장하고 그 다음 문자가 digit이면 pop하여 list에서 제거한 뒤 최종적으로 string으로 concat 해서 반환한다.

class Solution:
    def clearDigits(self, s: str) -> str:
        stack = []
        
        for char in s:
            if char.isdigit():
                if stack:  # 숫자가 나오면 이전 문자 삭제
                    stack.pop()
            else:
                stack.append(char)
        
        return ''.join(stack)

# 테스트 코드
sol = Solution()
print(sol.clearDigits("ab1c3d"))  # "cd"

• 시간 복잡도 : O(N) -> 한 번만 순회
• 공간 복잡도 : O(N) -> 리스트 사용

Code

class Solution:
    def clearDigits(self, s: str) -> str:
        indicies = []
        isDigit = False
        idx = 0

        while(idx < len(s)):
            if s[idx].isdigit():
                s = s[:(idx-1)] + s[idx+1:]
                # print(idx, s)
                idx = 0  
            idx += 1
                
        return s

 

Complexity

Time Complexity

모든 문자에대해서 digit을 만날때마다 다시 순회한다.

최악의 경우 n의 길이만큼 n번 반복하므로 O(N^2)

 

Space Complexity

새로운 문자열을 생성하므로 O(N)