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

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

프로그래머스

 

number의 자리수는 2자리 이상, 100만자리 이하 이므로 모든 경우를 구해서 최대값을 구하게 되면 무조건 시간초과가 발생한다.

 

따라서 최적의 경우를 구할 수 있는 그리디 알고리즘을 생각해야 한다.

 

EX)

4177252841
K=4

 

K가 4 이므로 최종 숫자의 길이는 10-4=6이 되어야 한다.

 

여섯자리 숫자를 구해야 하므로 처음의 (41772) 중에서 시작점을 구해야 한다.

만약5가 시작점이 된다면 여섯자리 숫자를 만들 수 없기 때문이다.

 

가장 큰 수를 최종 결과로 구해야 하므로 주어진 (41772)에서 가장 큰 수를 시작점으로 설정하면 된다!

 

(41772)52841 ==> 7

 

417(725)2841 ==> 77

 

4177(252)841 ==> 775

 

417725(28)41 ==> 7758

 

41772528(4)1 ==> 77584

 

417725284(1) ==> 775841

 

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        StringBuilder answerBuilder = new StringBuilder();
        int len = number.length()-k; // k개를 제거했을때의 자리수
        int start=0;
        
       for(int i=0; i<len; i++){
           int max=0;
           for(int j=start; j<=i+k; j++){
               if((int)number.charAt(j)>max){
                   max=(int)number.charAt(j);
                   start=j+1;
               }
           }
          answerBuilder.append((char)max);

       }
         answer = answerBuilder.toString();
        return answer;
    }
}