Remove K Digits

Q: Remove K Digits의 시간 복잡도는 얼마인가요?

단조 스택을 사용하면 n 개의 숫자에 대해 O(n) 시간에 실행됩니다. 각 숫자는 한 번 푸시되고, 각 팝은 k 번의 제거 중 한 번을 사용합니다. 스택에는 최대 n 개의 숫자가 들어가므로 추가 공간은 O(n) 입니다. 제거할 때마다 왼쪽부터 다시 탐색하면 O(n·k) 의 비용이 듭니다.

보통단조 스택 그리디

+10

숫자로 이루어진 문자열 num과 정수 k가 주어집니다. 정확히 k개의 숫자를 제거하고 나머지는 원래 순서대로 유지하여, 남은 숫자가 가능한 한 가장 작아지도록 하세요.

앞에 0이 붙지 않는 문자열로 반환하세요. 아무것도 남지 않거나 0만 남으면 "0"을 반환하세요.

함수

removeKdigits(num: string, k: integer) → string

numstring: 숫자 문자열로 쓴 숫자
kinteger: 제거할 자릿수
반환값string: 앞에 0이 붙지 않는 문자열로 나타낼 수 있는 가장 작은 수

제약 조건

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num은 숫자 0부터 9까지만 담습니다.
num에는 앞에 오는 0이 없습니다. 단, 숫자 자체가 0인 경우인 "0"은 예외입니다.

예제

입력: num = "4325043"k = 3
출력: "2043"
설명: 4와 첫 번째 3을 제거하면 2가 맨 앞에 옵니다. 0은 맨 앞에 올 수 없습니다. 그 앞에 네 자리가 있고 제거 횟수는 세 번이기 때문입니다. 마지막으로 제거되는 숫자는 5이며, 이 숫자는 더 작은 0 앞에 있습니다.

입력: num = "30200"k = 1
출력: "200"
설명: 3을 제거하면 0200이 되고, 앞의 0을 빼면 200입니다. 다른 숫자를 제거하면 3이 앞에 남아 3000과 같은 네 자리 숫자가 됩니다.

입력: num = "52"k = 2
출력: "0"
설명: 두 숫자가 모두 제거되므로 아무것도 남지 않으며 답은 "0"입니다.

후속 질문

대신 k자리 숫자를 제거하고 가장 큰 수를 남기려면 어떻게 해법을 바꾸면 될까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

가장 왼쪽에 있는 숫자의 자릿값이 가장 크므로, 오른쪽 이웃보다 큰 첫 번째 숫자를 제거해야 합니다. 유지할 숫자를 스택에 쌓으면 이 규칙을 문자열 전체에 한 번만 적용할 수 있습니다. 마지막까지 남은 제거 횟수만큼 뒤에서 숫자를 제거하고, 맨 앞의 0은 마지막에 제거합니다.

한 번에 숫자 하나씩 제거하기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

한 번에 숫자 하나씩 제거합니다. num[i] > num[i+1]인 첫 번째 위치 i를 찾아 num[i]를 삭제하고, 숫자가 내림차순이 되는 곳이 없다면 마지막 숫자를 삭제합니다. 이를 k번 반복합니다.

모든 답은 n-k개의 숫자를 유지하므로, 두 답이 다른 첫 번째 위치의 숫자가 어느 답이 더 작은지 결정합니다. i까지 숫자는 내림차순이 아니므로, 더 앞의 숫자를 삭제하면 그 자리에 적어도 같은 크기의 숫자가 들어오고, 더 뒤의 숫자를 삭제하면 큰 num[i]가 그대로 남습니다. num[i]를 삭제하면 줄일 수 있는 가장 앞선 위치의 숫자가 작아집니다.

숫자를 하나 제거할 때마다 왼쪽부터 다시 살펴보고 그 뒤의 숫자들을 이동시키므로, 작업량은 O(n·k)입니다. 40,000개의 1에서 k = 25,000이면, 탐색 과정에서 약 6.9 × 10^8개의 숫자를 읽습니다.

알고리즘

삭제할 수 있는 목록에 숫자를 복사합니다.
k번 반복합니다. 왼쪽부터 훑어가며 다음 숫자보다 큰 첫 번째 숫자 또는 마지막 숫자를 찾아 삭제합니다.
앞에 있는 0을 제거하고, 아무것도 남지 않으면 "0"을 반환합니다.

def removeKdigits(num, k):
    digits = list(num)
    for _ in range(k):
        # Find the first digit that is bigger than the digit after it.
        # If the digits never go down, i stops on the last digit.
        i = 0
        while i + 1 < len(digits) and digits[i] <= digits[i + 1]:
            i += 1
        del digits[i]
    result = "".join(digits).lstrip("0")
    return result if result else "0"

유지된 숫자의 단조 스택

핵심 아이디어

느린 버전이 num[i]를 삭제한 뒤에도 i 앞의 숫자들은 여전히 감소하지 않으므로, 다음으로 감소하는 부분은 간격 바로 앞의 숫자에서만 시작할 수 있습니다. 스택에는 그 접두 부분, 즉 아래에서 위로 갈수록 감소하지 않는 숫자들을 저장합니다. 새 숫자가 맨 위 숫자보다 작으면, 맨 위 숫자는 느린 버전이 삭제할 숫자의 오른쪽 이웃보다 큽니다. 맨 위 숫자를 꺼내고 삭제 횟수를 하나 사용한 다음, 새로운 맨 위 숫자가 여전히 더 크면 계속 꺼냅니다.

k = 3일 때 4325043에서는 3이 4를 꺼내고, 2가 3을 꺼내며, 0이 5를 꺼냅니다. 4와 3은 차례로 들어가서 2043이 됩니다.

각 숫자는 한 번씩 스택에 들어가고, 꺼낼 때마다 k번의 삭제 중 한 번을 사용하므로, 이 과정은 O(n)입니다.

알고리즘

빈 숫자 스택을 만듭니다.
num의 각 숫자에 대해: 제거 횟수가 남아 있고 스택의 맨 위 숫자가 현재 숫자보다 크면 맨 위 숫자를 꺼내고 제거 횟수를 하나 사용합니다. 그런 다음 현재 숫자를 스택에 넣습니다.
반복문이 끝난 후 제거 횟수가 남아 있으면 스택의 맨 위에서 그 횟수만큼 숫자를 제거합니다.
스택을 아래에서 위로 읽고, 앞에 오는 0을 건너뛴 다음 나머지를 반환합니다. 남은 숫자가 없으면 "0"을 반환합니다.

def removeKdigits(num, k):
    stack = []  # kept digits, never decreasing from bottom to top
    for digit in num:
        # A bigger digit right before a smaller one: dropping it makes the number smaller.
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # The kept digits never decrease, so any removals left come off the end.
    stack = stack[:len(stack) - k]
    result = "".join(stack).lstrip("0")
    return result if result else "0"

함정과 경계 사례

맨 위 값이 새 숫자와 같을 때 꺼내는 것. k = 1일 때 112에서는 12가 남지만, 정답은 11입니다.
반복문이 끝난 뒤 남은 제거 횟수를 처리하지 않거나, 앞에서 제거하는 것. 스택이 줄어들지 않으므로 마지막 숫자들을 제거하면 됩니다. k = 3일 때 123456789는 123456이 됩니다.
앞의 0을 제거 횟수로 세는 것. k = 1일 때 100200에서 제거되는 숫자는 1뿐입니다. 앞의 0들은 횟수 차감 없이 제거되므로 정답은 200입니다.
빈 문자열을 반환하는 것. k = 1일 때 10에는 0만 남으므로 정답은 "0"입니다.
num을 정수로 변환하는 것. 숫자가 4 × 10^4자리까지 있을 수 있어 어떤 정수형의 범위도 훨씬 넘어가므로, 숫자를 문자로 비교하세요.

자주 묻는 질문3

Remove K Digits의 시간 복잡도는 얼마인가요?

단조 스택을 사용하면 n개의 숫자에 대해 O(n) 시간에 실행됩니다. 각 숫자는 한 번 푸시되고, 각 팝은 k번의 제거 중 한 번을 사용합니다. 스택에는 최대 n개의 숫자가 들어가므로 추가 공간은 O(n)입니다. 제거할 때마다 왼쪽부터 다시 탐색하면 O(n·k)의 비용이 듭니다.

Remove K Digits에서 앞에 오는 0은 어떻게 처리하나요?

먼저 숫자를 제거하고, 끝에 있는 0만 제거하세요. 앞에 있는 0은 값을 바꾸지 않으므로 제거 횟수에 포함되지 않습니다. k = 1일 때 10200은 0200이 된 다음 200이 됩니다. 제거한 후 아무것도 남지 않으면 "0"을 반환하세요.

K개의 숫자 제거 문제를 추가 공간 O(1)로 해결할 수 있을까요?

네, 입력을 변경해도 된다면 가능합니다. 스택에는 지금까지 읽은 숫자보다 더 많은 숫자가 절대 들어가지 않으므로, 스택은 숫자 배열의 앞부분 자체에 둘 수 있고, 맨 위를 가리키는 인덱스 하나만 있으면 됩니다. 불변 문자열을 사용하는 언어에서는 숫자를 한 번 복사해야 하며, 이는 O(n)입니다.

def removeKdigits(num, k):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

num = "4325043"
k = 3

예상 출력

"2043"