큰 수 만들기

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

프로그래머스

 

숫자의 자리는 바꾸지 않고, k개의 숫자를 제거 했을 때의 숫자가 가장 큰 값을 찾는 문제.

 

어떤 수는 앞에 위치한 숫자가 클 수록 더 커지기 때문에, 탐욕법으로 앞자리부터 큰 수를 찾아나가면 된다.

 

다만 무한정 큰 수를 찾으면 제거해야하는 숫자가 k개보다 많거나 적어질 수 있으므로, 현재 체크해야할 수의 자릿수가 제거해야할 숫자만큼은 남아야 한다. 이점을 고려해서 작성하면... 타임아웃이 뜬다.

 

9를 만나면 다음 자리로 갈 필요없이 그 수가 가장 크다고 보면 되기 때문에, 이 점만 if로 분기처리해주면 된다.

 

class Solution {
    public String solution(String number, int k) {
        
        String ans = "";
        
        int len = number.length() - k;
        
        int curr = 1;
        int lt = 0;
        
        while (curr <= len) {
            char max = '0';
            
            for (int i = lt; i < k + curr; i++) {
                char num = number.charAt(i);
                if (num == '9' || num - max > 0) {
                    max = num;
                    lt = i + 1;
                    if (num == '9') break;
                }
            }
            
            curr++;
            ans += max;
        }
        
        return ans;
    }
}