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

문제

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

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

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

제한 사항

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

풀이

function solution(number, k) {
  let numberArr = number.split("").map((e) => +e);
  let stack = [];

  for (let i = 0; i < numberArr.length; i++) {
    while (k > 0 && stack[stack.length - 1] < numberArr[i]) {
      stack.pop();
      k--;
    }
    stack.push(numberArr[i]);
  }
  stack.splice(stack.length - k, k);
  //1000, 4321 같이 내림차순으로 숫자를 입력받은 케이스
  return stack.join("");
}

해설

기본적인 풀이법은 현재 숫자와 다음수를 비교하여 다음수가 더크면 현재수를 제거하는 것.

배열(stack)을 하나 생성한 다음 입력으로 받은 number에서 하나씩 넣어준다. 첫번째 요소는 그냥 들어갈 것이고 다음부턴 현재 요소와 stack에 마지막으로 들어간 요소를 비교해준다.

입출력 1을 예로 설명하면

1. 1이 stack에 삽입
2. 9와 1을 비교, 1을 제거하고 9를 삽입. k--(빼야하는 횟수)
3. 2와 9를 비교, 2를 삽입.
4. 4와 2를 비교, 2를 제거하고 4를 삽입. k--, 반복문 탈출.

이제 stack에 남아있는 요소를 문자열로 바꾸면 '94'가된다.

return문 이전에 코드를 보자
stack에서 stack의 길이에서 k를 뺀 값부터 k개를 잘라낸다. 이 코드가 있는 이유를 예제로 설명하겠다.
'4321', k=2 일 경우

비교하고 삽입하는 과정에서 항상 전 요소가 다음 요소보다 크다(= 내림차순으로 정렬되어있다.)

2개를 제거해주기 위해 stack의 길이 : 4 에서 k : 2 를 빼주고 거기서 k : 2개를 제거해줘야 답이 된다.