[LeetCode] 402. Remove K Digits (Daily Question)

문제

---

 

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

 

숫자 문자열 num에서 k개의 digit(0-9)을 없애서 가장 작은 수를 만드는 문제이다.

 

Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

 

풀이

---

아이디어

가장 큰 자릿수가 작아야 작은 수가 된다.

따라서 가장 큰 자릿수부터 살펴보며 k를 있는 대로 사용해 가장 작게 만들면 된다.

 

코드

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        answer = []

        # 큰 자릿수부터 살펴봄
        for n in num:
            # 다음 자릿수의 수가 더 작을 경우 현재 자릿수 삭제
            # 반복 (k 소모)
            while answer and k and answer[-1] > n:
                answer.pop()
                k -= 1
            
            answer.append(n)
        
        # 리스트 -> 문자열 변환
        answer = ''.join(answer)
        # k가 남았을 때 뒷부분을 자름
        if k: answer = answer[:-k]
        # 앞에 0이 있을 때 없앰 (0123은 123이니까)
        answer = answer.lstrip("0")
        # 비어있을 때 0 반환
        return answer if answer else "0"

---

 

후기

---

난이도

아이디어를 바로 떠올리지 못해 조금 애먹었다.

 

k개의 후보를 놓고 가장 작은 경우를 선택하는 방식으로 구현했으나,

몇 가지 경우에서 시간초과가 나 다른 방식을 생각하다가 성공한 방식을 떠올리게 되었다.

 

아이디어를 구현하는 것은 쉽지만, 언어 숙련도가 부족하다면 후처리과정에서 바로 떠올리기 힘들 수도 있다.

 

예외사항은 k가 남았을 경우, 앞에 0이 붙은 경우, 빈 문자열을 반환하게 될 경우 정도가 있다.

조금 귀찮아질순 있지만 까다로운 정도는 아니다.

 

다른 풀이

for문으로 문자열을 순회하는 것이 아닌, num을 리스트로 만들어 pop을 사용하며 구현할 수도 있다.

다만, pop을 사용하는 방식이 속도가 더 느리다.