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

문제 : 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

풀이 : 그리디 알고리즘을 접목하여, 현재 숫자보다 뒤에 더 큰 숫자가 있으면 현재 숫자를 지우는 방식으로 진행했다. 

단, 이미 내림차순으로 정렬되어있어 k가 남았을 경우 뒤에서부터 지우도록 로직을 추가해주었다. 

 

*charAt() : 문자열에서 특정 인덱스에 위치하는 유니코드 단일 문자 반환

 

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        char[] result=new char[number.length()-k];
        Stack<Character> stack=new Stack();
        
        for(int i=0; i<number.length(); i++){
            char c=number.charAt(i);
            // 스택이 비어있지 않고, 지울 수 있는 횟수가 남아 있고, 스택 맨 위 숫자가 현재 숫자보다 작으면 제거
            while(!stack.isEmpty() && k>0 && stack.peek()<c){
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        
        //이미 내림차순으로 정렬되어있어 k가 남았을 경우 뒤에서부터 지움
        for(int i=0; i<result.length; i++){
            result[i]=stack.get(i);
        }
        return new String(result);
    }
}

 

---

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42883