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

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

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

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb=new StringBuilder("");
        int answer_size=number.length()-k;
        int idx=0;
        Stack<Integer> stack=new Stack<>();
        while (idx<number.length()){
            int n=number.charAt(idx)-'0';
            while (!stack.empty() && stack.peek()<n && k>0){    //stack에 있는 값이 n보다 작으면 그값을 뺌
                stack.pop();
                k--;
            }
            stack.push(n);
            idx++;
        }
        while (!stack.empty()){
            sb.insert(0,stack.pop());
        }
        return sb.substring(0,answer_size).toString();
    }
}

어렵다 어려워..

처음엔 priority queue를 이용해서 숫자가 큰 순서->숫자가 같다면 나오는 순서가 빠른 순서부터 해서 골라서 더하고, 남은 값들은 다시 pq 안에 넣어서 조건에 맞는 수(범위가 맞는가, 지금 뽑았던 수보다 이전에 나온 수는 아닌가)를 체크해서 answer에 append해주는 방식을 택했는데.. 테스트 케이스 4개에서 시간초과가 났다..

여러번의 삽질을 계속 한후... 힌트를 보게 되었고 포인트는 "이전 수보다 큰 수가 나왔으면 그 이전 수를 제거" 해주는 아이디어이다..

 

수를 계속 순차적으로 넣기 전, stack의 top과 비교해 stack top이 현재 수보다 작으면 그 수를 빼준다. k-- 해줘서 뺀 횟수를 체크해준다. 

stack을 이용해 지역적으로 최대인 값을 구할 수 있다. 

단 여기서 빼주는 조건은 k>0 여야 한다는 것이다.