[프로그래머스] 탐욕법(Greedy) - 큰 수 만들기 (JavaScript)

문제 설명

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

---

풀이

스택을 이용해 풀어보자. 스택 후입선출에 유념하며 문제를 풀어야 한다. 그림을 그리면서 풀면 이해가 더 잘된다.

• 제거할 수 있는 개수는 k개이고 k가 모두 소진되면 더이상 제거할 수 없다.
• 스택은 후입선출이다.

단계

1. 스택에 아무 것도 담기지 않았을 경우 or 스택에 있는 숫자보다 넣으려는 숫자가 더 작은 경우 그냥 스택에 담는다.
   위 조건에 따라 1이 가장 처음 스택에 담겼을 것.

2. 다음 숫자는 9다. 1과 9를 비교했을 때 9가 더 크므로 스택에서 1을 제거하고 9를 담는다.
   숫자 1을 제거했으므로 이제 제거 가능 횟수는 1회 남음 (k: 1)

3. 다음 숫자는 2다. 9와 2를 비교했을 때 스택에 담긴 9가 더 크므로 2를 9 다음에 넣는다. 제거한 숫자가 없으므로 k는 여전히 1이다.

4. 다음에 숫자는 4다. 4와 2를 비교했을 때 4가 더 크므로 스택 맨 뒤에 있는 2를 제거하고 4를 넣는다.
   삭제 가능한 개수 모두 소진 (k는 0이 되었다.)

5. 스택에 있는 9와 4를 합쳐 문자열로 만들어준다.

코드

const number = "1924";
const k = 2;

function solution (number, k) {
  const numArr = number.split(''); // ["1", "9", "2", "4"]
  const stack = [];

  for (let idx in numArr) {
    
    // 스택에 있는 마지막 숫자가 스택에 넣으려는 숫자보다 작은 경우
    // 스택에 있는 마지막 숫자를 꺼내서 제거
    while ( stack.length > 0 && stack[stack.length - 1] < numArr[idx] ) {
      // console.log(stack[stack.length - 1], numArr[idx])
      if (k === 0) {
        // 제거할 수 있는 개수가 모두 소진됨 (k=0)
        // 더이상 숫자 제거할 수 없음
        break;
      } else {
        stack.pop();
        // 숫자 하나가 제거됐을 때
        // 제거할 수 있는 개수(k=2)에서 1씩 빼준다.
        k--;
      }
    }
    
    // [while 반복문 조건에 해당하지 않는 경우]
    // 스택에 아무것도 안 담겨있거나 or
    // 스택에 있는 숫자보다 스택에 넣으려는 숫자가 작거나 같은 경우 
    // 그냥 스택에 담는다.
    stack.push(numArr[idx]);
  }
	
  // 넣으려는 숫자가 스택에 있는 숫자보다 작으면 
  // 그냥 계속 담기므로 출력해야 하는 만큼 잘라서 사용
  stack.splice(stack.length - k, k);
  // 스택에 담긴 두 숫자를 합쳐 문자열로 만든다. 
  // ["9", "4"] -> "94"
  let answer = stack.join('');
  return answer; // "94"

}

solution(number, k);

---

문제 출처
https://programmers.co.kr/learn/courses/30/lessons/42883