문제

Programmers, 큰 수 만들기

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 어떤 숫자에서 K개의 수를 제거했을 때 얻을 수 있는 가장 큰 수를 구해야 한다.
• 가장 큰 수가 되려면 앞자리 수가 가장 커야 한다. 따라서 K개의 수를 지울 때 왼쪽부터 시작하여 큰 수가 등장하면 큰 수 이전에 등장한 수를 K개 지우면 된다. 예를 들어 "1924"인 경우 9가 등장했을 때 앞자리 수 1을 지운다. 4가 등장했을 때 2를 지우면 "94"가 남아 최댓값이 된다.
• 큰 수가 등장했을 때 큰 수로 시작하는 수가 최댓값이 되므로 큰 수보다 작은 이전 숫자들을 지우면 된다. 효과적으로 숫자를 삽입하고, 삭제하기 위해 vector 자료구조를 사용한다. stack 연산을 쓰지만 vector를 사용하는 이유는 문자열의 초기 순서를 유지하기 위함이다. 예를 들어 "1924"의 경우 94지만, 스택을 사용하면 49로 뽑아내기 때문이다. (물론 스택을 꺼내서 큐에 담고 다시 이를 꺼내는 작업을 해도 된다)

개선

코드

시간복잡도

• $O(N)$

C++

#include <string>
#include <vector>
#include <iostream>

using namespace std;

string solution(string number, int k) {
    string ans = "";
    vector<char> s;
    int n = number.length();
    int size = n - k;
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && s.back() < number[i] && k > 0) {
            s.pop_back();
            --k;
        }
        s.push_back(number[i]);
    }
    for (int i = 0; i < size; ++i)
        ans += s[i];
    return ans;
}

Java

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder ans = new StringBuilder();
        int n = number.length();
        int size = n - k;
        ArrayList<Character> s = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            while (!s.isEmpty() && s.get(s.size() - 1) < number.charAt(i) && k > 0) {
                s.remove(s.size() - 1);
                --k;
            }
            s.add(number.charAt(i));
        }
        for (int i = 0; i < size; ++i)
            ans.append(s.get(i));
        return ans.toString();
    }
}