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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=java 

프로그래머스

큰 수를 만드는 문제

 

풀이

스택을 사용하여 풀이하였다.로직은 다음과 같다.

1. 주어진 길이가 백만이니 선형 탐색 O(N) 으로 풀어야 한다.
2. 스택의 top 숫자가 현재 숫자 number.charAt(i) 보다 작으면 크거나 같은 숫자가 나올때까지 pop 을 한다. 
3. k만큼 제거 한 이후는 스택의 숫자를 합쳐서 리턴한다.
4. 모든 숫자가 내림차순이라서 한번도 pop 되지 않았을 경우 예외처리 한다

 

코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        //idx, val
        Stack<Character> st = new Stack<>();
        st.push(number.charAt(0));
        
        for(int i =1 ;i < number.length() ;i++){
            int c = number.charAt(i) - '0';
            while(!st.isEmpty() && st.peek()-'0' < c && k > 0){
                st.pop();
                k--;
            }
            st.push(number.charAt(i));
            
        }
        String ans ="";
        if ( k > 0){   
        for(int i = 0 ; i <number.length() - k ; i++){
            char x = number.charAt(i);
            ans += x;
        }
        }else{
            for(char x : st){
                ans += x;
            }
        }
        return ans;
    }
}