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

 

프로그래머스

처음에 완전 탐색으로 풀었다가 몇몇 테스트 케이스에서 시간 초과가 나서 그리디로 변경해서 푼 문제이다. 

 

- 한 번 탐색 시 한 자릿수의 최대값을 찾아야함

- 한 번 탐색 시 탐색 범위는 '탐색할 한 자릿수를 제외한 나머지 자릿수를 문자열의 마지막에 몰아넣은 상태에서 남는 모든 자릿수'임.

- 예를 들어, number = 4177252841, k = 4인 경우 첫 번째 반복 시 41772까지 탐색하고, 52841은 뒤에 몰아넣은 상태에서 41772에서의 최대값인 첫번째 7을 결과에 추가함. 두 번째 반복 시에는 뒤에 2841을 몰아넣은 상태에서 두 번째 7부터 시작하는 725를 탐색하여 최대값인 7을 추가함. 이런식으로 보존해야할 문자열 길이가 0이 될때까지 반복하여 최대값을 도출함.

- 예외처리 : 자릿수가 9인 경우 무조건 최대값이므로, 탐색 중간에 break하는 것이 성능에는 좋으나 이 코드에서는 예외처리를 하지 않아도 아슬아슬하게 통과가 됨

 

Note

- 스택을 사용해서 푼 사람들도 있었는데 탐색으로 끝내는 게 속도면에서는 더 유리한 것처럼 보인다.

import java.util.*;

class Solution {
    public String solution(String number, int k) {        
        
        int len = number.length() - k - 1;
        int idx = 0;
        
        StringBuilder sb = new StringBuilder();
        
        while(len >= 0){
            char max = '0';
            for(int i = idx; i < number.length() - len; i++){
                if(number.charAt(i) > max){
                    max = number.charAt(i);
                    idx = i + 1;
                    if(number.charAt(i) == '9'){
                        break;
                    }
                }    
            }
            sb.append(max);
            len--;
        }  
        
        return sb.toString();
    }      
}