[Lv2] 큰 수 만들기

프로그래머스

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

나의 풀이(1) ❌

처음에 풀때에는 어떻게 접근해야할지 몰라서 다른 풀이를 검색해보고 스택을 사용한다는 힌트를 얻었다. 그래서 다음과 같이 풀이를 작성했는데 12번 테스트케이스가 통과하지 않았다.

const solution = (number, k) => {
  const nums = number.split("").map((el) => Number(el));
  const res = [];
  for(let i=0; i<nums.length; i++) {
    while(k>0 && nums[i]>res[res.length-1]){
      res.pop();
      k--;
    }
    res.push(nums[i]);
  }
  return res.join("");
}

나의 풀이(2) ⭕

다른 분들이 작성한 예외케이스를 살펴보니 "1000",1의 경우, while문에 걸리는 조건이 없어서 [1,0,0,0]이 되고, 1000을 리턴하게 된다. 이는 1개의 숫자를 제거하지 못했으므로 오답이다. 따라서, 배열을 k개 제거한 개수만큼 잘라서 join하여 리턴시켜야한다.

const solution = (number, k) => {
  const nums = number.split("").map((el) => Number(el));
  const res = [];
  for(let i=0; i<nums.length; i++) {
    while(k>0 && nums[i]>res[res.length-1]){
      res.pop();
      k--;
    }
    res.push(nums[i]);
  }
  return res.slice(0, res.length-k).join(""); //수정한 부분
}

다른 분의 풀이 ⭕

count라는 변수를 사용하여 숫자를 제거한 횟수가 k와 일치하면 숫자가 저장된 stack과 number배열을 i번째까지 잘라 합쳐 리턴한다. 그래서 다른 풀이들보다 for문을 적게 돌기 때문에 시간이 많이 단축됐다. 10번 테스트케이스가 가장 오래걸리는데, 17ms정도 소요되어 나의 풀이가 46ms가 걸린 것과 비교해 30ms정도 빠르다.

const solution = (number, k) => {
  const stack = [];
  let count = 0;
  for(let i=0; i<number.length; i++) {
    const item = number[i];
    if(stack.length === 0) {
      stack.push(item);
      continue;
    }
    while(stack[stack.length-1] < item) {
      stack.pop();
      count++;
      if(count===k) return stack.join("")+number.slice(i);
    }
    stack.push(item);
  }
  return stack.slice(0, number.length-k).join("");