Funcia
Lv.2greedymonotonic-stackstackstring

숫자 K개를 지워 가장 작은 수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

가게 진열대의 가격표에 숫자 num이 적혀 있습니다. 점장님은 이 가격표에서 숫자 정확히 k개를 지워 가격을 최대한 낮추려고 합니다. 숫자를 지운 뒤 남은 숫자들의 순서는 바꿀 수 없습니다.

지우고 남은 숫자들로 만들 수 있는 가장 작은 수를 문자열로 반환하세요.

  • 결과의 맨 앞에 붙은 0은 모두 없앱니다. 예를 들어 남은 숫자가 "0200"이면 "200"을 반환합니다.
  • 남은 숫자가 없거나 모두 0이면 "0"을 반환합니다.

입출력 예

numkresult
"1432219"3"1219"
"10200"1"200"
"10"2"0"

입출력 예 설명

예 1 — 4, 3, 그리고 두 번째 2를 지우면 "1219"가 되고, 이보다 작게 만들 수는 없습니다.

예 2 — 맨 앞의 1을 지우면 "0200"이 남고, 앞의 0을 없애면 "200"입니다.

예 3 — 숫자를 모두 지우면 아무것도 남지 않으므로 "0"입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(num: string, k: int) → string

제한 사항

  • 1≤1 \le num.length ≤200,000\le 200{,}000
  • num은 숫자(0~9)로만 이루어져 있고, num이 "0"이 아니라면 0으로 시작하지 않습니다.
  • 0≤0 \le k ≤\le num.length

기대 복잡도

시간
O(N)
공간
O(N)

입출력 예

numk기대 출력
"1432219"3"1219"
"10200"1"200"
"10"2"0"

힌트

힌트

자릿수가 같다면 앞자리가 작을수록 작은 수입니다. 그래서 앞에서부터 보면서, 바로 다음 숫자보다 큰 숫자가 있으면 그 숫자를 지우는 것이 항상 이득입니다.

"맨 앞에서부터 처음으로 줄어드는 곳을 찾아 지우기"를 k번 반복하면 매번 처음부터 다시 훑어 O(Nk)O(Nk)가 되어 시간 초과가 납니다.

대신 스택에 숫자를 하나씩 쌓으세요. 새 숫자보다 큰 숫자가 스택 위에 있고 아직 지울 개수가 남아 있다면 꺼내서 지웁니다. 끝까지 본 뒤에도 지울 개수가 남으면 스택의 뒤쪽(가장 큰 쪽)에서 지웁니다. 모든 숫자가 한 번 들어가고 한 번 나오므로 O(N)O(N)입니다.

마지막에 앞의 0을 떼고, 비었으면 "0"을 반환하는 것을 잊지 마세요.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4013판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.