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

문제 출처

프로그래머스 lev2 - 큰 수 만들기

나의 풀이(실패)

다른 풀이(통과)

그리디. stack에 push/pop하면서 최적의 해를 판단한다.

• push할 때 더 큰 게 있으면 pop (pop할 때 k 차감)
• 그게 아니라면 push

지나간 값들에 대해 판단하기에는 배열 자료구조가 가장 좋은 것 같다.

function solution(number, k) {
  const stack = [];
  let answer = '';

  for(let i=0; i<number.length; i++) {
    const now = number[i];

    while(k > 0 && stack[stack.length-1] < now) {
      stack.pop();
      k--;
    }
    stack.push(now);
  }
  stack.splice(stack.length-k, k);
  answer = stack.join('');
  return answer;
}
// console.log(solution("1924", 2)) // "94"
console.log(solution("1231234", 3)) // "3234"
// console.log(solution("4177252841", 4)) // "775841"

splice(i,1)보다 pop()이 더 빠르다.

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)
}

참고

프로그래머스 - 큰 수 만들기 (javascript)