문제

링크

풀이

K개의 수를 제거하여 만들 수 있는 숫자들 중에서 가장 큰 수가 무엇인지를 구하려 했다. (완전탐색!) 하지만 시간초과의 위험성이 무조건 발견되어 다른 방법으로 풀었다. (1,000,000 x 999,999 x ... 만 해도 시간초과가 발생할 것이라는 예측이 가능하다...)

가장 먼저 생각할 수 있는 것은 단어길이(number) - K = 정답의 길이라는 사실을 알 수 있다. 즉, 정답의 길이만큼 반복문을 수행하여 만들 수 있는 큰 수를 고르면 된다. 대신 탐색의 범위가 중요하다!

예를 들어 설명하자면

1231234 이고 K=3 일 때, 우리는 4개의 숫자를 골라야한다.
먼저 첫 번째 숫자를 고른다. ( 주의사항 ) 이 때 뒤에 최소 3개의 숫자를 뽑는 것을 보장해야한다!
따라서 첫 번째 탐색범위는 1231에서 가장 큰 수 1개를 골라야한다!

1. 1231 (1231234)에서 첫 번째 가장 큰 숫자 선택 --> 3이 된다.

2. 3의 다음 숫자인 1과 2사이에서 (1231234) 가장 큰 숫자 선택 (뒤에 최소 2개의 숫자를 뽑는 것을 보장해야한다!) --> 2가 된다.

3. 3과 3사이에서(1231234) 가장 큰 숫자 선택 (뒤에 최소 1개의 숫자를 뽑는 것을 보장해야한다. 따라서 고를 수 있는 선택지가 3 하나 밖에 없다.) --> 3이 된다.

4. 4가 된다.

String answer = ""에 max를 추가하여 답을 도출하도록 코딩하였으나 시간초과가 발생하였다. 따라서 시간을 줄이기 위해 StringBuilder를 사용하였다.

또 다른 사람들의 풀이를 보니 Stack을 이용한 풀이가 있었다! 다음에는 Stack을 이용하여 풀어보아야겠다...!

코드

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();
        int answer_Length = number.length() - k;

        int start = 0;
        int end = number.length() - answer_Length;
        int idx = 0;

        while (answer_Length > 0) {
            int max = -1;
            for (int i = start; i <= end; i++) {
                int num = number.charAt(i) - '0';
                if (num > max) {
                    max = num;
                    idx = i;
                }
            }
            start = idx + 1;
            answer_Length--;
            end = number.length() - answer_Length;
            sb.append(max);
        }

        return sb.toString();
    }
}