[Greedy] programmers(프로그래머스) - 큰 수 만들기

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

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

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

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예
number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

---

import java.util.Stack;

public class Solution {
    public String solution(String number, int k) {
        Stack<Character> stack = new Stack<>();

        for (char digit : number.toCharArray()) {
            // 현재 스택의 마지막 요소가 현재 숫자보다 작고, 제거할 수가 남아 있을 때
            while (!stack.isEmpty() && k > 0 && stack.peek() < digit) {
                stack.pop();
                k--;
            }
            stack.push(digit);
        }

        // 남은 수 k가 있다면 마지막 숫자들을 제거
        while (k > 0) {
            stack.pop();
            k--;
        }

        // 스택에 남아 있는 숫자들을 문자열로 변환
        StringBuilder result = new StringBuilder();
        for (Character ch : stack) {
            result.append(ch);
        }

        return result.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.solution("1924", 2));        // "94"
        System.out.println(sol.solution("1231234", 3));     // "3234"
        System.out.println(sol.solution("4177252841", 4));   // "775841"
    }
}

 

Greedy 전략을 효율적으로 구현하기 위해 Stack을 사용한 문제이다.

스택을 사용하면 순서를 유지하면서도, 후입선출(LIFO) 구조를 통해 현재 숫자보다 작은 숫자를 빠르게 제거할 수 있다.

 

예시: "1924", k = 2

스택을 사용하지 않고 단순히 for문으로 처리한다면:

• 1과 9를 비교해서 9를 살리고 1을 제거
• 9와 2를 비교하고, 9가 크므로 그대로 둠
• 2와 4를 비교해서 4가 크므로 2를 제거

이 과정에서 앞쪽 숫자와 계속 비교해야 하므로 비효율적임

 

스택을 사용하면:

1. 스택이 비어 있으니 1을 넣음 → [1]
2. 다음 숫자 9가 스택의 맨 위 1보다 크므로 1을 제거하고 9를 넣음 → [9]
3. 숫자 2를 넣음 → [9, 2]
4. 숫자 4가 스택의 맨 위 2보다 크므로 2를 제거하고 4를 넣음 → [9, 4]

최종적으로 스택에 남아 있는 [9, 4]가 답이 된다.

 

이처럼 스택을 사용하면 한 번에 숫자 비교와 제거를 처리할 수 있어 효율적이다!