프로그래머스 큰 수 만들기 (Level2 Java)

https://school.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는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.
입출력 예
number k return
"1924" 2 "94"
"1231234" 3 "3234"
"4177252841" 4 "775841"

---

문제 해결을 위한 과정

이 문제는 스택을 활용하여 해결할 수 있습니다.

1. 순차 탐색: 숫자를 앞에서부터 하나씩 확인합니다.
2. 비교 및 제거:
   • 스택이 비어있지 않고, k가 남아있으며, 스택의 최상단(top) 숫자가 현재 숫자보다 작다면? 스택을 pop() 하고 k를 하나 줄입니다. 이 과정을 조건을 만족할 때까지 반복합니다.
3. 추가: 현재 숫자를 스택에 넣습니다.
4. 남은 k 처리: 모든 숫자를 돌았는데 아직 k가 남았다면, 뒤에서부터 남은 k만큼 잘라줍니다. (반례 처리 위함)

---

반례 찾기

1. 내림차순을 입력해 보았는가? 

가장 흔한 반례는 숫자가 계속 작아지는 경우입니다.

• 입력: number = "9876", k = 2
• 사고: 현재 숫자보다 스택에 있는 숫자가 항상 크기 때문에 pop()이 한 번도 일어나지 않습니다.
• 결과: 9876이 그대로 출력된다면 오답입니다. 정답은 98이어야 합니다.
• 해결: 루프가 끝난 뒤에도 k가 남았다면 그만큼 뒤를 잘라줘야 합니다.

2. 모든 숫자가 같은 경우

• 입력: number = "5555", k = 2
• 이 경우도 내림차순과 마찬가지로 제거 로직을 타지 않습니다.

위 두가지 경우는 그리디 문제의 반례를 찾아내는 단골 이므로 해당 방법을 숙지하여야 합니다.

---

소스코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        
        
        for(int i = 0; i < number.length(); i++) {
            int num = number.charAt(i) - '0';
            if(stack.isEmpty()) {
                stack.add(num);
            } else {
                if(stack.peek() >= num) {
                    stack.add(num);
                } else {
                    while(k > 0 && !stack.isEmpty() && stack.peek() < num) {
                        stack.pop();
                        k -= 1;
                    }
                    stack.add(num);
                }
            }
        }
        
        if(k > 0) {
            stack.pop();
            k -= 1;
        }
        for(Integer n : stack) {
            sb.append(String.valueOf(n));
        }
        answer = sb.toString();
        return answer;
    }
}