[Programmers] LV2 - 큰 수 만들기

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

코딩테스트 연습 - 큰 수 만들기

 

 

알고리즘 분류 : 그리디 알고리즘

 

문제 파악

처음으로 생각했던 것은 가장 작은 숫자부터 1개씩 제거해볼까 하는 생각이 들었다.

하지만 입출력 예제 3번에서 1,2를 제거할 경우 477584가 나오므로 775841보다 작은 숫자가 나오기 때문에 아니었다.

 

그 뒤로 생각난 것이 스택

 

각 자리의 숫자를 스택에 넣고 Peek() 데이터와 비교하여 작을 경우 현재 위치의 숫자보다 작은 것을 제거해 나간다

3번 예제를 보면

Stack : 4

Stack : 4,1로 쌓이다가 7은 4,1 모두 7보다 작으니 Stack에서 제거 한 다음 7을 Stack에 Push 해준다.

해당 로직을 반복으로 하고 제거한 개수가 k개가 된 이후는 Stack에 push 해준다.

 

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        String answer = "";

        StringBuilder sb = new StringBuilder();

        Stack<Character> st = new Stack<>();

        int loop = number.length() - k;

        for (int idx = 0; idx < number.length(); idx++) {
            char c = number.charAt(idx);

            while (!st.isEmpty() && st.peek() < c && k-- > 0) {
                st.pop();
            }
            st.push(c);
        }


        for (int idx = 0; idx < loop; idx++) {
            sb.append(st.get(idx));
        }
        answer = sb.toString();

        return answer;
    }
}