[프로그래머스] 큰 수 만들기 - JAVA

문제

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

프로그래머스

 

풀이

제거할 문자 K개를 찾는다는 말은 포함할 문자가 NUMBER길이 - K 개라는 뜻이다.

따라서 for문을 이용하여 포함할 문자의 개수만큼 포함할 문자를 찾는다.

두번째 for문의 범위는 탐색해야하는 문자의 시작(index)부터, k+i까지 탐색을 해야한다.

(k+i까지 탐색해야 포함할 문자를 number-k개 찾을 수 있다) 

그리고 index에는 가장 큰수 다음 index를 넣어준다. 이유는 그 다음 문자열부터 가장 큰 수를 찾아야하기 때문이다.

주의 해야 할 것은 String으로 문자열을 만드는 것보다 StringBuilder로 만들어야 시간초과가 안난다.

 

예를 들어,

'4177252841' 를 0번 index부터 탐색을 시작하여 총 6자리의 return 값을 만들어야 하기 때문에 뒤에서 6번째에 위치한 '41772' 까지 탐색을 진행한다.

그리고 StringBuilder에 가장 큰 수를 append한다.

딧; 탐색할 시작 index는 가장 큰 수였던 3번인덱스 다음인 4번인덱스 부터 순회한다.

'7252841' 문자열을 탐색하는것이다.

그러면 앞의 규칙에 따라 뒤에서 5번째에 위치한 '725' 까지 탐색을 진행하고 가장큰수를 append한다.

그 다음은 '252841' 문자열을 뒤에서 4번째인 '252' 까지,

그 다음은 '2841' 문자열을 뒤에서 3번째인 '28' 까지,

그 다음은 '41' 문자열을 뒤에서 2번째인 '4' 까지,

그 다음은 '1' 문자열을 뒤에서 1번째인 '1' 까지,

모든 범위가 끝나게되면 현재까지 진행했던 가장큰수를 이어붙인 '775841'가 만들어질것이고

return 해주면 된다.

 

 

코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();
        
        int idx = 0;   
        for(int i=0;i<number.length()-k;i++){
            char max = '0';
            for(int j=idx;j<=k+i;j++){
                if(max < number.charAt(j)){
                    max = number.charAt(j);
                    idx = j+1;
                }
            }
            
            sb.append(max);
            // System.out.println(idx +" "+(i));
            if(idx == number.length() - i+1){
                sb.append(number.substring(idx));
                break;
            }
        }
        
        return sb.toString();
    }
}