[프로그래머스] 큰 수 만들기 - Java

• 문제

• 가장 작은 부분문제를 떠올리는 부분이 생각보다 무척 어려웠다.

  • 문제의 조건을 정리하면 아래와 같이 표현할 수 있다.
    • 앞으로 숫자를 더 지워야 할 때 어떤 숫자의 앞에 그 숫자보다 작은 숫자를 두지 않는 것
  • 이를 전개하면, 아래와 같은 로직을 만들 수 있다.
    • 앞에서부터 계속 두 개의 숫자를 비교하여
    • 앞의 숫자가 작으면 버리고, 아니면 취한다
  • 하지만 문제 풀이를 떠올리는 과정에서 특정 상황별 대처 방법을 같이 떠올리고 추가하려고 하다 보니 자연스럽게 가장 작은 부분문제에서 멀어지는 문제가 발생하였고, Greedy한 풀이에서 자꾸만 멀어지는 모습을 확인하였다. Greedy 알고리즘 문제풀이 연습이 좀 더 필요할 것 같다.

코드

• 제출 후 다른 풀이를 찾아보니 굉장히 깔끔한 풀이가 있어서 이를 참고하여 코드를 다시 정리하였다. 이렇게 굉장히 심플하고 깔끔한 풀이를 바닥부터 직접 해낼 수 있도록 더 노력해야겠다.

import java.util.Stack;
import java.util.stream.Collectors;

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

        int countRemoved = 0;
        for (char ch : number.toCharArray()) {
            while (!stack.isEmpty() && stack.peek() < ch && countRemoved < k) {
                stack.pop();
                countRemoved++;
            }

            stack.push(ch);
        }

        return stack.subList(0, number.length() - k)
                .stream()
                .map(Object::toString)
                .collect(Collectors.joining(""));
    }
}

결과