[프로그래밍 문제] 큰 수 만들기

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

number k return
"1924" 2 "94"
"1231234" 3 "3234"
"4177252841" 4 "775841"

생각한 방법

1. 앞에서부터 k+1개까지의 수 중 가장 큰수를 뽑아
2. 가장 큰 수 +1 위치에서부터 k가 0이 될때까지 반복

import java.util.stream.*;
class Solution {
    public String solution(String number, int k) {
        StringBuilder num = new StringBuilder();
        int start = 0;
        while(k > 0){
            if(start+k >= number.length()) {start = number.length(); break;}
            int max = IntStream.rangeClosed(start, start+k)
                .mapToObj(x->x)
                .parallel()
                .max((x, y)->number.charAt(x)-number.charAt(y))
                .get();
            k -= max-start;
            start = max+1;
            num.append(Character.getNumericValue(number.charAt(max)));
        }
        num.append(number.substring(start));
        return num.toString();
    }
}

결과

정확성  테스트
테스트 1 〉	통과 (5.10ms, 78.7MB)
테스트 2 〉	통과 (6.86ms, 79.7MB)
테스트 3 〉	통과 (9.76ms, 80.6MB)
테스트 4 〉	통과 (24.89ms, 81MB)
테스트 5 〉	통과 (21.56ms, 73.1MB)
테스트 6 〉	통과 (155.26ms, 149MB)
테스트 7 〉	통과 (213.47ms, 219MB)
테스트 8 〉	통과 (507.98ms, 413MB)
테스트 9 〉	통과 (27.93ms, 93.9MB)
테스트 10 〉	통과 (6136.27ms, 396MB)
테스트 11 〉	통과 (5.04ms, 76.9MB)
테스트 12 〉	통과 (4.56ms, 75.6MB)

풀이 설명

문자열 수정이 빈번히 일어나므로 문자열을 가변적으로 수정 가능한 StringBuilder를 이용한다.
start 변수는 시작점으로 인덱스 0에서부터 가장 큰 수를 찾는다.

1. max 변수는 Stream을 이용해 start에서 start+k까지의 범위중 가장 큰 수의 인덱스로 초기화된다.
2. max보다 앞에 있는 값들은 모두 제거하므로 k값을 max보다 앞에있는 값들 개수만큼 빼준다.
3. start 값을 max위치 +1로 변경한다.
4. StringBuilder 객체에 max값을 추가한다.

위 과정을 반복하는데 start+k값이 number의 길이 이상인 경우는 모든 k를 제거한 것을 의미하므로, start를 number의 길이로 설정하고 과정을 종료한다.