큰 수 만들기 JAVA

문제

프로그래머스

String 형식으로 숫자가 최대 1백만 길이가 올 수 있다.

그 중에서 k개의 숫자를 제거해 남은 문자열중 가장 큰 문자열을 출력하면 되는 문제이다.

예를 들어 문자열이 "4177252841" 총 10개의 문자열이고, k = 4라면

최종 6개의 문자열 중에 가장 큰 수를 출력하는 것이다.

정답은 "775841" 이다.

 

이 문제에서 어려웠던 점은 3가지 이다.

1) 어떻게 최댓값을 구해야 하는가?

2) 문자열의 인덱스가 왔다갔다 하므로 일반화 식이 필요하다.

2) 마지막에 문자열을 출력하는데 StringBuilder를 사용하지 않아 시간초과가 발생했다.

 

처음에 생각한 방식은 문자열의 인덱스 처음부터 끝까지 순회하면서 

현재 남은 문자열과 내가 출력해야할 문자열의 개수를 계속 비교하면서 최댓값을 구하는 것이다.

이것은 구현하기 매우 어려웠다.

 

두번째 방법은 그리디 하게 접근했다.

위의 예시로 "4177252841" 이고 k = 4라면  우리는 총 6개의 문자열을 만들어야 한다.

따라서 "4177252841" 빨간색으로 색칠한 부분만 6자리 문자열중에 첫째 자리에 갈 수 있다. answer = "7"

"4177252841" 바로 7이다. 이제 7이후에 5자리 문자열만 찾으면 된다.

"7252841" 여기서는 7이 가장 크다. answer = "77" 이제 7이후에 4자리 문자열만 찾으면 된다.

"252841" 여기서는 5가 가장 크다. answer = "775" 이제 5이후에 3자리 문자열만 찾으면 된다.

"2841" 여기서는 8이 가장 크다. answer = "7758" 이제 8이후에 2자리 문자열만 찾으면 된다.

"41" 여기서는 4가 가장 크다. answer = "77584" 이제 4이후에 1자리 문자열만 찾으면 된다.

"1" 여기서는 1이 가장 크다. answer = "775841" 끝

 

이것을 코드로 구현하자.

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder(); //정답을 담아줌
        int len = number.length() - k; // k개를 제외한 실제 길이

        int start = 0;
        for(int i=0;i<len;i++){
            char c = '0';
            for(int j = start;j <= i + k;j++){ //여기서 이제 최댓값 찾음
                if(number.charAt(j) > c){
                    c = number.charAt(j);
                    start = j+1;
                }
            }
            answer.append(Character.toString(c));
        }
        return answer.toString();
    }
}

주의 해야 할 점은 StringBuilder를 사용하지 않으면 시간초과가 발생한다.