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

문제 설명

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

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

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

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

풀이

처음에는 해괴망측한 방법으로 풀려했다.(지금 기억이 안남)
그러다가 질문하기에 어떤분이 스택으로 풀면 된다. 라는 글을 읽고 바로 해결책을 알아냈다!

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

  for (const num of number) {
    if (stack.length === 0) {
      stack.push(num);
      continue;
    }

    let lastStackIndex = stack.length - 1;
    const numToNumber = Number(num);

    while (lastStackIndex >= 0 && k > count) {
      if (Number(stack[lastStackIndex]) < numToNumber) {
        stack.pop();
        count++;
      }
      lastStackIndex--;
    }
    stack.push(num);
  }

  if (k > count) {
    const lastStackIndex = stack.length;

    stack.splice(lastStackIndex - (k - count), lastStackIndex);
  }
  return stack.join('');
};

처음은 무조건 stack에 값을 넣어줘야하니 stack의 길이가 0이면 무조건 push 시켜주고 continue 해줬다.

그러고 stack의 마지막 인덱스를 구한 후 그때의 stack의 값과 현재의 num 값을 비교해서 num이 더 큰 경우에만 pop을 해준다. 이제 stack의 인덱스 0까지 비교를 한 후 while문을 빠져나오는 형태로 했다.

for...of 문이 끝난 후 k만큼 수를 제거하지 못했을 경우에 제거하기 위해 splice로 뒤에서부터 제거해야할 수 만큼 잘라줬다.

이렇게하면 해결!!! 인 줄 알았지만... 테스트 케이스 10번에서 자꾸 시간 초과가 났다.

while문에 문제가 있었다. 처음에 작성한 while문은 stack 끝까지 다 돌아봐야했기 때문에 엄청나게 긴 문자열을 제시하는 테케 10번에서 시간 초과가 뜨게된것이다.

다음으로 바꾸니까 바로 해결이 됐다.

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

  for (const num of number) {
    if (k === number.length - stack.length) break;
    if (stack.length === 0) {
      stack.push(num);
      continue;
    }

    const numToNumber = Number(num);

    while (numToNumber > stack[stack.length - 1] && k > count) {
      stack.pop();
      count++;
    }
    stack.push(num);
  }

  return stack.join('');
};

stack의 마지막 값과 현재 num을 비교하고 num이 클 경우엔 pop을 한다. 이때 조건문으로 stack의 마지막 인덱스와 num을 계속 비교를한다.

예를 들어서 "987632"에서 3개의 수를 제거한다고하자. 맨 처음에 9를 stack에 넣고 다음을 진행한다. 그 다음 stack에 담겨 있는 9와 현재 num인 8을 비교했을때 num이 stack의 마지막 값보다 작기 때문에 num을 stack에 넣어준다.
그 다음 숫자인 7이 stack의 마지막 값인 8보다 작으니 while문이 동작하지 않고 바로 stack에 넣어준다.

만약 처음의 while문 조건식으로 했다면 무조건 while문이 동작하고 불필요한 연산을 하게 된다.
이런 연산때문에 시간초과가 뜨지 않았나싶다.