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

문제 링크

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 함수를 완성하세요.

 

제한 조건

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

내 풀이

function solution(number, k) {
  let numberArray = number.split("");
  let stack = [];

  for (let i = 0; i < numberArray.length; i++) {
    while (
      k > 0 &&
      stack.length > 0 &&
      stack[stack.length - 1] < numberArray[i]
    ) {
      stack.pop();
      k--;
    }
    stack.push(numberArray[i]);
  }

  // 'k'가 여전히 남아있다면 가장 뒷부분의 숫자 제거
  while (k > 0) {
    stack.pop();
    k--;
  }

  // 스택이 비어있다면 0을 반환
  return stack.length === 0 ? "0" : stack.join("");
}

• Stack을 활용한 풀이법입니다.

  for (let i = 0; i < numberArray.length; i++) {
    while (
      k > 0 &&
      stack.length > 0 &&
      stack[stack.length - 1] < numberArray[i]
    ) {
      stack.pop();
      k--;
    }
    stack.push(numberArray[i]);
  }

• number의 길이만큼 반복문을 먼저 돌립니다.
• while문의 조건을 k > 0, stack.length > 0 및 stack의 마지막 수가 넣을려고 하는 수보다 작다면 stack의 마지막을 빼고, k도 감소시킵니다.
• while문이 끝나면 스택에 숫자를 대입시킵니다.

다른 사람의 풀이

const solution = (number, k) => {
    const stack = [];
    let count = 0;
    for (let i = 0; i < number.length; i++) {
        const item = number[i]
        // stack이 초기에 비어있으면 push 한다.
        if (stack.length === 0) {
            stack.push(item)
            continue;
        }
        // stack에 쌓인 최근 값이 들어와야할 값보다 크거나 같을때까지 꺼낸다.
        while (stack[stack.length - 1] < item) {
            stack.pop()
            count++
            // 만약 숫자를 빼야할만큼 뺐다면 완성된 값을 반환한다.
            if (count === k) return stack.join("") + number.slice(i, number.length)
            // 스택이 비어있으면 루프를 멈추고 스택에 아이템을 추가한다.
            if (stack.length === 0) break;
        }
        stack.push(item)
    }
    // 만약
    return stack.join("").slice(0, number.length - k + count)
}

오늘 배운 점

탐욕법에만 집중하다보니, Stack을 활용할 방법을 상기시키지 못했습니다.

문제를 풀 때, 내가 알고 있는 자료구조나 알고리즘을 좀 더 활용하는 방법이 필요할 것 같습니다.