큰 수 만들기 - (다시 보기)

문제

풀이

class Solution {
    public String solution(String number, int k) {

        StringBuilder answer = new StringBuilder();
        int start=0;
        
        while(start<number.length() && answer.length() < (number.length()-k)){
            int leftNum = k + answer.length() + 1;
            int max =0;
            for(int i=start; i<leftNum; i++){
                if(max < number.charAt(i)-'0'){
                    max = number.charAt(i)-'0';
                    start = i+1;
                }
            }
            answer.append(Integer.toString(max));
        }
        
        return answer.toString();
    }
}

그리디,, 최선의 방법을 찾아야 한다. 처음에 이런저런 방식으로 시도했는데 다 실패. 다음 방식도 시간초과 실패. 해결하기 위해서 인터넷을 참고..

해결방법

테스트 케이스 10번이 되게 시간이 오래걸리기 때문에 StrungBuilder를 이용해 시간을 단축시킨다.

number = "4177252841", k = 4

• 현재 내가 뽑아야 할 숫자의 갯수는 6개로, 맨 뒤부터 5자리 수는 남겨둔다.
• (그래야 숫자 1개를 뽑더라도 뒤 5자리가 남아 무사히 6자리를 만들 수 있다.)
• "4177252841"에서 "52841"을 빼고 "41772"에서 가장 큰 수를 찾는다.
• 가장 큰 수 7을 뽑아 answer에 붙여준다. 이 때 7의 index는 2, 그 전 문자들은 다 지워준다. (순서가 중요하기 때문에 7을 뽑은이상 어차피 뒤의 숫자를 가지고 만들 수 없다.) answer ="7";
• 417을 지운 후 "7252841"에서 "2841"을 빼고 "725"에서 가장 큰 수를 찾는다.
• 7을 뽑아 붙여준다. answer = "77" 뽑은 7 이전의 숫자들은 다 버린다.
• "252841"에서 "841"을 빼고 "252"에서 가장 큰 수를 찾는다.
• 5를 뽑아 붙여준다. answer = "775" 뽑은 '5'이전의 숫자들은 다 버린다.
• "2841"에서 "41"을 빼고 "28"에서 가장 큰 수를 찾는다.
• 8을 뽑아 붙여준다. answer = "7758" 뽑은 '8'이전의 숫자들은 다 버린다.
• "41"에서 "1"을 빼고 "4"에서 가장 큰 수를 찾는다.
  이러한 방식으로 4와 1을 붙여 answer = "775841"을 만든다.

다시 보자.