[프로그래머스] 가장 큰 수 만들기

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int deleteCount =0;
        StringBuilder sb = new StringBuilder(number);
        
        for(int i=0; i<number.length()-1; i++){
            if(deleteCount == k ){
                break;
            }
            if(sb.charAt(i)<sb.charAt(i+1)){
                sb.deleteCharAt(i);
                deleteCount ++;
                i=-1; // 다시 처음부터 비교
            }
            
        }  
        answer = sb.toString();
        answer = answer.substring(0,number.length()-k); //내림차순 정렬되어있어서 deletecount가 줄지않았을경우 
        return answer;
    }
}

 

Test Case 10 : 시간초과 

 

수정코드

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int deleteCount = 0;
        int idx=1;
        StringBuilder sb = new StringBuilder(number);
        
        while(deleteCount != k){
            if(idx >= 1 && sb.charAt(idx-1)<sb.charAt(idx)){
                sb.deleteCharAt(idx-1);
                deleteCount ++;
                idx--;
            }
            else{
                /* idx가 끝값까지 갔을때 deleteCount가 도달되지 못했을때 */
                if(idx == sb.length() - 1 && sb.charAt(idx) <= sb.charAt(idx-1)) {
					return sb.toString().substring(0,number.length()-k);
				}
				else { // idx가 0 일때 다시 다음값부터 비교할 수 있도록 1 증가시킴 
					idx ++;
				}
            }    
        }
        
        answer = sb.toString();
        
        
        return answer;
    }
}

숫자를 줄여 나가던 중 뒤에값이 앞에값보다 작거나 같은경우가 지속되어 

answer의 길이가 number-k길이보다 길어지게 되면 쓸데없는 시간이 걸린다.

확정된 answer의 길이가 number-k길이만큼 되면 거기서 substring을 통해 답을 확정 짓고 끝낸다.