큰 수 만들기

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42883

❔ 문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

⚠️ 제한사항

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.

• k는 1 이상 number의 자릿수 미만인 자연수입니다.

---

💡 풀이 (언어 : Java & Python)

단순해 보이는 문제지만 굉장히 어려웠다. 타인의 풀이를 참고해서 다시 작성해 보았다. 직전 수들을 stack에 쌓아놓고 뒤에서 더 큰수가 나오면 stack의 수들과 비교해 작은 수들을 모두 stack에서 제거해준다. 뒤의 수가 stack의 수보다 작으면 그냥 stack에 추가해준다. k만큼 제거를 다 못했으면 뒤에서 남은 k만큼 빼준다.

Java

class Solution {
    public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < number.length(); i++) {
            char c = number.charAt(i);
            // 뒤의 수가 앞의 stack의 수보다 크면 stack에서 작은 수 제거
            while (!stack.isEmpty() && stack.peek() < c && k > 0) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        // k만큼 위에서 제거 못했으면 뒤에서 남은 수 만큼 빼주기
        for (int i = 0; i < result.length; i++)
            result[i] = stack.get(i);
        return new String(result);
    }
}

Python

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        # 뒤의 수가 앞의 stack의 수보다 크면 stack에서 작은 수 제거
        while len(stack) != 0 and stack[-1] < num and k > 0:
            stack.pop()
            k -= 1
        stack.append(num)
    # 위에서 k만큼 제거 다 못했을 경우 뒤에서 남은 수만큼 빼주기     
    if k != 0:
        stack = stack[:-k]
            
    return "".join(stack)