[스택, 그리디] 큰 수 만들기

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

첫풀이 (런타임에러 12번 케이스)

1. 앞에서부터 k개를 제거해야하므로 앞에서부터 순회한다
2. 앞의수(a)와 뒤의 수(b)를 비교해서
   1. a < b 이면 stack에서 a를 제거하고 b를 넣는다
3. 2번을 제거한 횟수가 k이하일때까지 반복한다.
4. k개를 제거한뒤 뒤에 남은 숫자가 있으면 뒤에 붙인뒤 반환한다.

function solution(number, k) {
  const arr = [...number].map(Number);
  let removeCount = 0;
  let stack = [arr[0]];
  let i = 1;

  // 앞에서부터 k개만 제거한다 0->1 1->2 2->3 3->4
  while (removeCount < k) {
    const curr = arr[i];

    // 전의값이 현재값보다 클때까지 전의값을 제거한다
    while (stack[stack.length - 1] < curr && removeCount < k) {
      stack.pop();
      removeCount++;
    }
    stack.push(curr);
    i++;
  }
  // k개를 제거하고도 아직 뒤에 남은 수가 있다면 붙여준다.
  if (i < arr.length) {
    stack = [...stack, ...arr.slice(i)];
  }
  return stack.join("");
}

 

반례

"4321", 1, "432" 처럼 앞의 숫자가 뒤의 숫자보다 작은 경우가 없는 경우, 즉 내림차순이여서 제거한 수가 없는 경우 while이 무한순회한다.

 

두번째풀이 (통과)

고친것: 숫자가 내림차순이여서 제거를 못 했을때, 뒤에 k개를 제외한 숫자를 리턴한다

function solution(number, k) {
  const arr = [...number].map(Number);
  let removeCount = 0;
  let stack = [arr[0]];
  let i = 1;

  // 앞에서부터 k개만 제거한다 0->1 1->2 2->3 3->4
  while (removeCount < k && i <= arr.length) {
    const curr = arr[i];

    // 전의값이 현재값보다 클때까지 전의값을 제거한다
    while (stack[stack.length - 1] < curr && removeCount < k) {
      stack.pop();
      removeCount++;
    }
    stack.push(curr);
    i++;
  }
  // 한개도 제거가 안 된 경우
  if (!removeCount) {
      return arr.slice(0, arr.length-k).join('')
  }
  // k개를 제거하고도 아직 뒤에 남은 수가 있다면 붙여준다.
  if (i < arr.length) {
    stack = [...stack, ...arr.slice(i)];
  }
  return stack.join("");
}

 

 

최종풀이(통과)

1. 앞의 수 < 뒤의수 일경우 앞의수를 제거한다
2. 1번을 모든 수간에 비교하는데 제거한 횟수가 k를 넘어가지 않을때까지 반복한다
3. 모든 숫자를 비교후 k > 0 이면 뒤에 붙여준다

function solution(number, k) {
    var answer = [];
    const stack = [];
    
    for (let i = 0; i < number.length; i++) {
        const curr = Number(number[i]);
        // [제거] 앞의수 > 뒤의수 일때까지
        while(stack.length && stack[stack.length-1] < curr && k > 0) {
            stack.pop();
            k--;
        }
        // [넣기]
        stack.push(curr);
    }
    // k가 남으면
    if (k > 0) {
        return stack.slice(0, stack.length-k).join('')
    }
    return stack.join('');
}