문제 설명

숫자 스트링과 지울 숫자갯수의 정보가 주어진다. 그러면, 이 숫자 스트링에서 지워야 하는 갯수만큼 지웠을때 가장 큰 수가 나오는 경우를 찾아라.

문제 접근

내가 접근한 방법은 다음과 같다.
1. 지워야 하는 갯수 + 1을 윈도우로 삼는다.
2. 주어진 문자열에서 해당 윈도우 내 최댓값이 위치한 인덱스를 찾는다.
3. 윈도우의 시작 지점부터 해당 인덱스 사이에 있는 값들은 모두 제거한걸로 취급하고, 가장 큰 수만 결과스트링에 넣는다.
4. 지워야 하는 갯수에서 이번에 지운 갯수를 빼서 업데이트하고, 이번턴에 찾은 가장 큰 값이 위치한 인덱스 + 1의 인덱스부터 다시 윈도우를 만들고 탐색을 1번부터 반복한다.

아래를 예로 들어보자.
"1231234"에서 3개를 지울 때 가장 큰 수는 "3234"

• 지워야 하는 갯수는 3이다. 그러므로 윈도우 크기를 4로 삼고, 1231을 본다.

• 이중 가장 큰 값은 3이다. 즉, 앞에 있던 12를 지운 셈친다.

• 지워야 하는 갯수는 이제 1개다. 이전턴에 찾은 가장 큰 값이 3이므로 그 다음 스트링인 "1234" 중 윈도우를 2로 삼고 "12" 중 가장 큰 값을 찾는다. 가장 큰 값은 2이므로 1을 지운다.

• 지울 갯수를 모두 채웠으므로, 남은 숫자들을 모두 붙여준다.

• 결과는 3234

풀이

import java.util.*;
import java.io.*;

class Solution {
    String number;
    public String solution(String number, int k) {
        this.number = number;
        StringBuilder sb = new StringBuilder();
        int reduceCount = 0;
        int curStart = 0;
        int windowSize = 0;
        while(reduceCount != k) {
            if (curStart + k-reduceCount == number.length()){
                curStart = number.length();
                reduceCount = k;
                break;
            }
            
            int maxIndex = findValueAndIndex(curStart, k-reduceCount + 1);
            reduceCount += (maxIndex - curStart);
            curStart = maxIndex + 1;
            sb.append(number.charAt(maxIndex));
        }
        
        if (reduceCount==k && curStart < number.length()) { 
            sb.append(number.substring(curStart, number.length()));
        }
        return sb.toString();
    }
    
    // 반환: 이번에 찾은 최댓값의 인덱스
    int findValueAndIndex(int start, int windowSize) {
        int maxIndex = start;
        int max = getNum(start);
        for(int i=start; i<start + windowSize; i++) {
            int iNum = getNum(i);
            if (iNum == 9) return i;
            if (iNum > max) {
                max = iNum;
                maxIndex = i;
            }
        }
        return maxIndex;
    }
    
    int getNum(int index) {
        return (int)number.charAt(index) - 48;
    }
}

내가 짠 이 로직은 다른 코드들에 비해 비록 (많이)길지만, 성능은 좋은 편에 속한다고 생각한다.
다른 사람들의 풀이와 비교하려고 여러 코드들을 실행해보았는데 2000ms 혹은 심하면 8000ms가 걸리기도 했지만 통과되는걸 확인했다.

오랜만에 다시 풀어봤더니 잘 안풀린다.

다른 사람들의 풀이를 봤다. 예전에 내가 어떻게 풀었던건지 좀 신기하다....
다른 사람들의 풀이는 간단했지만 시간 복잡도가 너무 컸다.
하지만, 의미는 있는 코드라고 생각하고 정리한다.

• 문제를 역 접근해서, 제거보다는 뽑는것에 초점을 둔다.
• 만약 총 a자리수를 찾아야하는 거라면, 그리고 이번에 그 a자리수 숫자의 가장 맨 앞 첫 숫자를 뽑는 차례라면, 우리는 남은 숫자에서 뒤의 a-1개 숫자를 안전영역으로 남기고, 앞에 있는 숫자들 중 가장 큰 수를 뽑아야 한다. 만약 이를 지키지 않고, 안전영역에 있는 숫자까지 포함해서 최댓값을 찾았다가 그 수가 만약 최댓값이라면 그 수를 뽑는 순간 뒤에 있는 남은 숫자를 다 뽑아도 a자리수의 숫자를 못만들기 때문이다.