자바(JAVA) - 큰 수 만들기(Programmers : 42883)

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

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

와 이건 dfs로 모든 조합 구해서 풀면 되겠다! 하고 풀었다가 좌절한 문제..

고수님들의 설명을 참고하여 그리디 알고리즘을 사용하여 더 간결하고 직관적인 코드로 답을 찾을 수 있었다..

 

number의 첫번째 숫자부터 순서대로 Stack에 넣어준 뒤, 

다음 인덱스의 숫자를 확인 할 때, 그 숫자가 마지막에 넣은 숫자보다 큰지 확인 후 바꿔주며 삭제된 숫자의 개수를 카운트해준다.

이렇게 카운트된 값은 삭제할 숫자 개수, k보다 작은지 비교해주기 위해 사용한다. 

상기 그리디한 작업을 반복하며, number의 길이 - k 길이를 유지해주며 stack에 값을 push하면 된다. 

 

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        int len = number.length();
        String answer = "";
        Stack<Integer> intStk = new Stack<Integer>();
        int delCount = 0;
        for (int i = 0; i < len; i++) {
            int currInt = Character.getNumericValue(number.charAt(i));
            while (!intStk.isEmpty() && delCount < k && currInt > intStk.peek()) {
                intStk.pop();
                delCount++;
            }
            if (intStk.size() < len - k) intStk.push(currInt);
        }  
        
        Iterator itr = intStk.iterator();
        while(itr.hasNext()) {
            answer += itr.next() + "";
        }
        
        return answer;
    }
    
}