[JS] 프로그래머스 코딩테스트 연습 | 탐욕법(Greedy) -큰 수 만들기

1. 문제

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

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

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

2. 입출력 예

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

---

3. 풀이

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

  for (const item of number) {
    // 스택의 마지막 요소가 item보다 작다면 스택의 마지막 요소를 지워줌
    while (count < k && stack[stack.length - 1] < item) {
      stack.pop();
      count += 1;
    }
    stack.push(item);
  }

  // count가 k까지 도달하지 못하는 경우 예)"9876543"
  while (count < k) {
    stack.pop();
    count += 1;
  }

  return stack.join("");
}

스택을 사용한 풀이
스택의 마지막 요소가 item보다 작다면 answer의 마지막 요소를 pop(), count +=1 해준다.

주어진 number가 오름차순으로 정렬된 숫자일 경우를 위해 k만큼 pop() 해주는 while문을 만든다.

마지막으로 stack 배열을 join("")으로 string으로 만들어준다.

---

다른사람풀이

function solution(number, k) {
  const answer = [];
  let head = 0;
  let del = k;

  while (answer.length < number.length - k || head < number.length) {
    if (del && answer[answer.length - 1] < number[head]) {
      answer.pop();
      del--;
      continue;
    }
    answer.push(number[head++]);
  }

  return answer.slice(0, number.length - k).join("");
}

answer 배열의 마지막 요소가 number[head] 보다 작으면 answer의 마지막 요소를 pop()하고 del -= 1해준다.

마지막에 return에서 slice를 해준 이유는
예를들어 "9876543" 이런식으로 오름차순 수가 주어진 경우 pop()되지 않기 때문에 slice(0, number.length - k) 해준 것