Lv.2greedymonotonic-stackstackstring
숫자 K개를 지워 가장 작은 수
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
가게 진열대의 가격표에 숫자 num이 적혀 있습니다. 점장님은 이 가격표에서 숫자 정확히 k개를 지워 가격을 최대한 낮추려고 합니다.
숫자를 지운 뒤 남은 숫자들의 순서는 바꿀 수 없습니다.
지우고 남은 숫자들로 만들 수 있는 가장 작은 수를 문자열로 반환하세요.
- 결과의 맨 앞에 붙은
0은 모두 없앱니다. 예를 들어 남은 숫자가"0200"이면"200"을 반환합니다. - 남은 숫자가 없거나 모두
0이면"0"을 반환합니다.
입출력 예
| num | k | result |
|---|---|---|
"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
제한 사항
-
num.length num은 숫자(0~9)로만 이루어져 있고,num이"0"이 아니라면0으로 시작하지 않습니다.-
knum.length
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| num | k | 기대 출력 |
|---|---|---|
"1432219" | 3 | "1219" |
"10200" | 1 | "200" |
"10" | 2 | "0" |
힌트
힌트
자릿수가 같다면 앞자리가 작을수록 작은 수입니다. 그래서 앞에서부터 보면서, 바로 다음 숫자보다 큰 숫자가 있으면 그 숫자를 지우는 것이 항상 이득입니다.
"맨 앞에서부터 처음으로 줄어드는 곳을 찾아 지우기"를 k번 반복하면 매번 처음부터 다시 훑어 가 되어 시간 초과가 납니다.
대신 스택에 숫자를 하나씩 쌓으세요. 새 숫자보다 큰 숫자가 스택 위에 있고 아직 지울 개수가 남아 있다면 꺼내서 지웁니다. 끝까지 본 뒤에도 지울 개수가 남으면 스택의 뒤쪽(가장 큰 쪽)에서 지웁니다. 모든 숫자가 한 번 들어가고 한 번 나오므로 입니다.
마지막에 앞의 0을 떼고, 비었으면 "0"을 반환하는 것을 잊지 마세요.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 13 | 판정만 |
| performance | 60 | 4 | 판정만 |