[2024] day 103. Leetcode 402. Remove K Digits

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 11일 (목)
Leetcode daily problem

402. Remove K Digits

https://leetcode.com/problems/remove-k-digits/?envType=daily-question&envId=2024-04-11

Problem

주어진 숫자에서 k개의 숫자를 제거하여 얻을 수 있는 가장 작은 숫자를 반환한다.

Solution

stack

해당 문제는 주어진 스택을 스택을 이용해 탐색하면서, 스택에 쌓인 숫자가 현재 숫자보다 크면 스택에서 숫자를 빼내는 방식으로 해결한다. 이를 통해서 스택에 가장 작은 숫자가 위에 위치하고 주어진 k 만큼의 숫자를 제거할 때 까지 반복한다.
이 후 스택에 쌓인 숫자를 조합해 최종 결과를 반환한다.

Code

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        for n in num:
            while k>0 and stack and stack[-1] > n:
                stack.pop()
                k-=1
            stack.append(n)
            
        while k>0:
            stack.pop()
            k-=1
            
        result = ''.join(stack).lstrip('0')
        
        if not result:
            return '0'
        
        return result

Complexicity

시간 복잡도

입력 문자열을 한번 순회하면서 스택에 문자를 쌓으므로, 문자열 길이에 해당하는 O(n) 의 시간복잡도가 걸린다.

공간 복잡도

문자열을 stack에 저장하므로 문자열 사이즈에 해당하는 공간복잡도인 O(n)이다.