시작하며 🔥

푼 건 1시간, 새롭게 풀려고 트라이 한 건 3시간이 걸렸네요 😅
덕분에 뭔가 그래도 어떻게 메모리 접근을 하는 게 좀 더 단축되는가를 경험할 수 있던 정말 귀한 시간이었어요.
어제 그리디 유사 문제(?)로 속상했는데, 오늘은 그래도 그리디를 제대로 만났네요!
일단 이 문제는 이를 알아도 시간 초과에 주의해야 해요. 일단 시작해보죠 !!

풀이과정 📃

저는 다음과 같은 생각을 했었어요.

93219321이라는 문자열이 있고, k는 4라고 하자.
그렇다면 최댓값은 9932일텐데, 이를 접근하는 방법은?
1. k + 1 개를 비교한다. (남아 있을 가장 큰 수 1개, 나머지 버릴 수도 있는 후보 4개)
2. 가장 큰 수의 인덱스를 구한다
3. 그렇다면 해당 인덱스가 맨 앞에 오면 된다! (가장 크게 해야 하니까요)
4. 그렇다면 현재 가장 큰 수의 인덱스에 +1을 해주자. (맨 앞의 9는 이미 확정)
5. answer에 9를 넣어주고 numberArr을 잘라주자.
6. 3219321에서 또 k + 1개를 비교하자! (아까 버린 게 없기에 k는 그대로 4)
7. 가장 큰 수의 인덱스는 9. 9가 앞에올 때까지 자른다.
8. 3개가 사라졌다. k에서 3개를 빼주자.
9. 9를 answer에 넣어준다. (현재: 99) 이후 또 numberArr을 잘라주자.
10. 이러한 방식을 계속 반복하다가, 결국에 numberArr과 k가 같아지면, 결국에는 이는 버려야 하는 숫자다. 결국 answer가 최적의 해다.

결국, 현재 선택할 수 있는 최선의 방법이 곧 최적의 해임이 성립하게 되므로 그리디를 만족합니다.

💡 하지만, 이를 주의해야 해요!

이 문제는 생각보다 시간 복잡도가 까다롭습니다. 저도 맨 처음에는 시간초과가...😂

그래서 고민을 해봤는데, for문을 통해 가장 큰 수를 가져올 때 (getMaxValue) 9가 나오면 바로 리턴을 하는 방식을 통해 조금이라도 줄여낼 수 있겠더라구요.

결과적으로 다음과 같은 코드가 완성됐어요!

function getMaxValue(number, from, to) {
    let max = 0;
    let end = Math.min(number.length, to);
    for(let i= from; i < end; i++) {
        if (number[i] === 9) return 9;
        if (max < number[i]) max = number[i];
    }
    return max;
}

const solution = (number, k) => {
    let answer = "";
    let numberArr = number.split("").map(value => parseInt(value));
    let lastIdx = 0;
    while(k !== 0) {
        if (numberArr.length === k) return answer;
        const maxValue = getMaxValue(numberArr, lastIdx, k+1);
        let maxValueIdx = numberArr.indexOf(maxValue);
        k -= maxValueIdx;
        answer += maxValue;
        numberArr.splice(0, maxValueIdx + 1);
    }
    return answer + numberArr.join("") ;
}

결과적으로 시간 내에 통과하네요...!

마치며

솔직히 정말 아쉬웠어요.
이후에 계속 splice처리하지 않고 진행하는 방법을 시도했거든요.
그런데 시간초과가 계속 뜨고 이 부분은 뜨지 않는 게, 아무래도 10번 케이스의 경우 무진장 길고, 계속해서 연산을 시도해야 하는 케이스인 것 같아요. (이때, 저는 numberArr의 길이를 줄였기 때문에 오히려 시간이 운좋게(?) 절약된 듯합니다.)

여튼, 이런 경우도 있구나!라는 것을 지금이라도 느낄 수 있어서 행복하네요. 👍
역시 알고리즘은 정말 재밌어요!