[프로그래머스/알고리즘 고득점 Kit] 탐욕법(Greedy) - 큰 수 만들기 (Java)

큰 수 만들기

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

---

풀이

앞자리가 클수록 전체 수가 커짐

• (`k > 0`) + (스택의 top(`stack.peekLast()`) < 현재 숫자(`n`)) 
  • `stack.pollLast()`: 스택 pop
  • `k--`
• 현재 숫자 push

for (char n : number.toCharArray()) {
    while (!stack.isEmpty() && k > 0 && stack.peekLast() < n) {
        stack.pollLast();
        k--;
    }
    stack.addLast(n);
}

---

예시

number: 1924 / k: 2

• 1
  • 빈 스택 -> push
    • stack = [1] / k = 2
• 9
  • top(1) < 9 -> pop 
  • k = 1
  • 빈 스택 -> push
    • stack = [9] / k = 1
• 2
  • top(9) > 2 -> X
  • push 
    • stack = [9, 2] / k = 1
• 4
  • top(2) < 4 -> pop
  • k = 0
  • push
    • stack = [9, 4] / k = 0

=> 94

---

코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        Deque<Character> stack = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();

        for (char n : number.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peekLast() < n) {
                stack.pollLast();
                k--;
            }
            stack.addLast(n);
        }

        while (k-- > 0) stack.pollLast();

        for (char s : stack) sb.append(s);

        return sb.toString();
    }
}