[프로그래머스 LV2] 큰 수 만들기

문제

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

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

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

첫 번째 시도

아이디어

전체 문자열에서 k 개의 문자를 제외해야 한다.
따라서 앞 자리부터 순회하면서 하나의 문자를 지운 문자열을 반환하는 함수 remove 를 만들고, 그 함수를 k 번 호출하는 방식으로 구현했다.

결과는 하나의 케이스에서 시간 초과가 발생했다.

소스코드

function solution(number, k) {
  const remove = () => {
    for (let i = 0; i < number.length - 1; i++) {
      if (number[i] < number[i + 1]) return number.substring(0, i) + number.substring(i + 1, number.length);
    }

    return number.substring(0, number.length - 1);
  };

  for (let i = 0; i < k; i++) {
    number = remove();
  }

  return number;
}

두 번째 시도

아이디어

이전 시도에서 문자열 자체를 만들고 반환하는 과정에서 연산에 부하가 생기는 것 같아서 문자열을 직접 만들지 않고 스택을 활용하기로 했다.

전체 문자열 number 를 순회한다.
1. 현재 순회중인 값이 스택의 최상단에 들어있는 값보다 작다면
  그대로 스택에 넣는다.
2. 현재 순회중인 값이 스택의 최상단에 들어있는 값보다 크다면
  자신보다 큰 값이 스택의 최상단에 존재할 때 까지 스택에서 꺼내고
  k 카운트를 감소시킨다.
  단, 제외해야 할 k 개의 문자를 이미 모두 처리했다면 더 이상 꺼내지 않는다.
순회를 마쳤으면, 제외해야 할 문자를 아직 모두 처리하지 않았을 케이스를 위해서 마지막에 있는 k 개의 문자를 제외한다.

소스코드

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

  for (const num of number) {
    while (stack.length > 0 && num > stack[stack.length - 1] && k > 0) {
      stack.pop();
      k--;
    }

    stack.push(num);
  }

  stack = stack.slice(0, stack.length - k);
  return stack.join('');
}