[leetcode] Remove K Digits

문제

• 문제 링크
• 문자열 num과 정수 k가 주어진다. num은 문자열이지만 숫자로 이루어져 있다. num에서 k개의 숫자(digit)를 제거해서 만들 수 있는 가장 작은 수를 구해야 한다.
• 제약 조건
  • num과 k의 범위: 1 <= k <= num.length <= 10^5
  • num에는 숫자만 들어간다.
  • num은 0을 제외하고는 0부터 시작하지 않는다.

풀이

풀기 전

• 우선 규칙을 먼저 찾아야 했다. 예시를 끄적이며 규칙을 찾아봤다. 이때 얻은 아이디어는 다음과 같다.
  1. 앞에서부터 지울 값을 찾아야 한다.
  2. 특정 값이 바로 뒤에 있는 값보다 크다면 지워야 한다.
• 두개의 예시인 12324와 13224를 생각해보면, 둘 다 3을 지웠을 때 가장 작은 값이 된다. 자릿수가 같을 때 앞에 있는 값이 작아야 최소값을 찾을 수 있기 때문이다.
• 처음에는 스택으로 구현했으나, k개의 숫자를 지운 뒤 스택에서 값을 빼내고 다시 reverse 해야해서 코드가 길어졌다. 그래서 StringBuilder 사용해서 다시 풀었다. 푸는 단계는 아래와 같다.
  • 1단계: 숫자를 순회하며 바로 뒤에텍스트 있는 값보다 큰 값을 지운다. 지워진 값의 앞에 값이 뒤에 있는 값보다 작거나 같을 때까지 반복한다. 최대 k개 지운다.
  • 2단계: 아직 k개가 지워지지 않았다면 뒤에서부터 남은 k개만큼 자른다. 뒤에 있는 값이 가장 큰 값이기 때문이다.
  • 3단계: 앞에 0부터 시작하는 구간을 자른다.

코드

class Solution {
    public String removeKdigits(String num, int k) {
    	// num 길이와 k가 같으면 다 지우는 거니까 0을 반환한다.
        if (num.length() == k)
            return "0";

        StringBuilder sb = new StringBuilder();
        for (int i=0; i<num.length(); i++) {
            char ch = num.charAt(i);
            // 1단계: StringBuilder 끝에 있는 값이 뒤에 넣을 값보다 작거나 같을 때까지 지운다.
            while (k > 0 && sb.length() != 0 && sb.charAt(sb.length() - 1) > ch) {
                sb.deleteCharAt(sb.length() - 1);
                k--;
            }
            //  StringBuilder 끝에 넣어준다.
            sb.append(ch);
        }

		// 2단계: k가 남아있는 만큼 뒤에서부터 자른다.
        String ans = sb.toString().substring(0, sb.length() - k);
        
        // 3단계: 앞에 0부터 시작하는 구간을 자른다.
        int i = 0;
        for (; i<ans.length() - 1; i++) {
            if (ans.charAt(i) != '0')
                break;
        }

        return ans.substring(i);
    }
}

푼 후

• 생각보다 쉽지 않았다. 처음에는 문제를 잘못 이해하기도 했다. 풀이를 제대로 찾았을 때도 엣지 케이스를 잘 고려하지 못했다. 고려해야 하는 케이스가 생각보다 많았다. 코딩 테스트에 나왔다면 잘 풀었어도 엣지 케이스를 고려하지 못해서 틀렸을 거 같다.
• num의 길이를 n이라고 하면, num을 한 번 순회하므로 시간 복잡도는 O(n)이다. 순회하는 도중에 while문이 있긴 하지만, 모든 숫자는 StringBuilder에 한 번 들어갔다가 최대 한 번 빠져나가므로 여전히 시간 복잡도는 O(n)이다. 공간은 문자열만큼만 사용하므로 공간 복잡도도 O(n)이다.