문제

어떤 숫자에서 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"

나의 코드 (테케 10 런타임 에러)

function solution(number, k) {
    number = number.split('').map(Number);
    const origianlL = number.length;
    const originalK = k;

    let ans = '';

    while(k > 0){
      if(ans.length === origianlL - originalK) return ans;
       const frontNums = number.slice().splice(0, k + 1);
        const maxIdx = frontNums.indexOf(Math.max(...frontNums));
        number.splice(0, maxIdx);
       ans += number.shift();
       k -= maxIdx;
    } 
    return ans + number.join('');

테케 10번에서 계속 런타임에러가 나는 원인을 아직 잡지 못했다.

처음에 테케 12번에서 시간초과가 났었는데,
number = "99999", k = 3과 같은 케이스가 있다고 가정하고 코드를 고쳐보니 12번은 통과가 되었다. while문 내에서 maxIdx가 계속 0이 나올텐데, while문 마지막줄인 k -= maxIdx가 계속 줄어들지 않을테니 무한정 반복문 돌려돌려가 될 것이기 때문이다. 그래서 while문 탈출 조건을 만들어주었다. 이럴 때는 ans.length가 의도했던 길이와 같아지면 바로 ans를 반환하면 된다.

if(ans.length === origianlL - originalK) return ans;

이렇게 예외 처리를 해주었지만!! 그렇지만!!
10번 케이스는 계속 런타임 에러가 난다.. 원인 불분명.. 만약 이글을 무심코 지나가는 고수님이 계시다면 적극적인 지적 감사하겠습니다..
결국 며칠 동안 고민해봐도 런타임에러로 통과하지 못한 코드는 과감히 버리고 질문하기에 있는 통과 코드를 보았다.

통과 코드 (내가 작성한 코드 아님 주의)

function solution(number, k) {
 let stack = [];

    let arr = number.split('').reverse();

    while(arr.length && k > 0){
        stack.push(arr.pop());
        while(stack[stack.length - 1] < arr[arr.length - 1] && k > 0) {
            stack.pop();
            k--;
        }
    }

    if(k !== 0) stack = stack.slice(0, -k);

    return stack.join('') + arr.reverse().join('');
}

스택으로 구현한 코드이다. 스택으로 하면 어떨까 생각만 하고 막상 구현은 못했는데, 배울 점이 많은 코드인 것 같다.

얼핏 봤을 때는 내가 떠올렸던 큰 수 만들기 방식이랑 비슷하다고 생각했는데, 뜯어보니 다르다. 내 코드는 앞에서부터 순회하면서 k + 1개 숫자 중 가장 큰 숫자 앞에까지 모두 지워버리는 방식이다. 앞의 숫자는 클수록 좋은데(탐욕스러운 탐욕법 문제), 최대 k개까지 밖에 지울 수 없으니까!

이 코드는 앞에서부터 시작해서 내 차례 숫자보다 그 다음 숫자가 더 크면 앞에 숫자를 모두 지워버리는 방식이다. 하나 지울 때마다 물론 k--를 해서 k = 0이 되면 남은 숫자들을 반환!

인상적이었던 것은 처음에 arr.shift()가 아닌 arr.pop()을 사용하기 위해 arr를 과감히 뒤집었다는 것이다. 나도 시간복잡도 생각해서 arr.pop() 쓰고 싶었지만 막상 못하고 arr.shift()를 썼다. 과감함에 놀라 일단 박수 치는 코린이👏🏻👏🏻

reverse 배열에 있는 원소를 마지막 원소부터 차례대로 stack에 push하고,(첫번째 숫자부터 push하는 것) 아직 arr에 남아있는 원소들 중 마지막 원소 (원래 숫자로 치면 남아있는 숫자 중 가장 앞의 숫자)와 비교한다. 이렇게 하면 인접한 원소들끼리 대소 비교를 할 수 있다. 남아있는 숫자 중 가장 앞의 숫자가 stack에 있는 숫자보다 더 크다면 stack에서 pop한다.

아직도 프로그래머스에 1~2개씩 테케 실패해서 해결하지 못하고 있는 문제들이 더러 있다.. 이제 아무리 두뇌 풀가동해봐도 최대 2시간동안 해결되지 않는 문제들은 과감히 답을 보기로 결정했다. 5시간 넘게 붙잡아봐도 해결이 될랑말랑한 문제들은 다 이유가 있는 것이었다. 이제 알고리즘 풀면서 필요할 때는 오기를 좀 덜어내는 연습도 하자 ㅎㅎㅎ.. 멘토님도 이를 적극 권장했다. 차라리 모범 답안을 보고 몰랐던 방식을 터득하는 게 더 도움이 되는 단계에 온 것 같다고 한다. 알고리즘 유형 별로 쓸 데가 많은 문제 풀이 방식들을 많이 접하고 흡수해야한다.

할 수 있숴 쟤스민!!!! 빠이팅!!!!