들어가며

가벼운 마음으로 들어갔다가 한 방 먹은 문제였다. 탐욕법을 집중적으로 공부하다가 만난 문제였다. 탐욕법이 얼핏 보기엔 쉬워보이는데 찬찬히 풀다보면 전혀 그렇지가 않다. 공식 같은 정해져있는 패턴이 있는게 아니라서 더 그런가.

문제

https://programmers.co.kr/learn/courses/30/lessons/42883

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

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

입출력 예

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

해설

해설 페이지를 보고 이 문제를 스택으로 접근하면 깔끔하게 해결된다는 것을 알았다. 모든 수를 하나씩 확인하면서 스택의 가장 윗 요소에 이전보다 작은 숫자가 들어있을 경우 그 요소를 제거하고 새로운 숫자를 넣는다. 큰 숫자를 확인한다는 목적만 생각하느라 숫자 하나하나를 볼 가능성을 놓쳤었다.

엣지 케이스는 처음 숫자가 들어온 후 계속 작은 숫자만 들어올 경우 stack에서 숫자들이 빠져나가질 못했다. k 만큼 버리질 못한다. stack.splice 구문으로 필요한 만큼만 잘라내고 반환했다.

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

  for (let i = 0; i < number.length; i++) {
    const target = number[i];

    while (k > 0 && stack[stack.length - 1] < target) {
      stack.pop();
      k--;
    }
    stack.push(target);
  }
  // 한 번도 stack.pop이 일어나지 않은 경우 splice로 잘라준다.
  // ex) 654321, 1
  stack.splice(stack.length - k, k);
  return stack.join('');
}

잘못된 풀이

처음엔 수의 범위를 정해놓고 그 안에서 가장 큰 수를 찾으면서 접근했다. 이렇게 하면 큰 수를 빠르게 찾을 수는 있지만 모든 숫자를 다 볼수는 없다. 첫번째로 큰 수를 찾느라 두번째로 큰 수를 놓치게 된다. 아무리 조건을 조정해도 해결이 안되더라.

function solution(number, k) {
  // * 가장 큰 수의 인덱스를 찾는 함수 선언
  function findMaxNumIdx(number) {
    let maxNumIdx = 0;
    for (let i = 0; i < number.length; i++) {
      if (number[maxNumIdx] < number[i]) maxNumIdx = i;
    }
    return maxNumIdx;
  }

  let result = '';
  let totalLength = number.length - k;
  let idx = 0;
  for (let i = 0; i < totalLength; i++) {
    let maxNumIdx = findMaxNumIdx(number.slice(idx, totalLength + i));
    result += number[idx + maxNumIdx];
    idx += maxNumIdx + 1;
  }
  return result;
}