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

처리조건

https://programmers.co.kr/questions/27691

풀이

number로 들어온 값을 인덱스0부터 돌면서 뒤에있는 숫자와 비교해 크다면 건드리지 않고 작다면 제거해나가야하며 제거이후에 다시 앞에 있는 숫자까지 검사해주어야한다. 아래를 확인해보자

k갯수만큼 제거되면 이제 남은 문자열을 돌려주어야 할 것이다. 문자열 하나하나 일단 for문으로 돌리기시작한다.

사전에 제거된 양을 변수로 잡고 제거될 때마다 ++하여 k만큼 제거되면 종료시킬 준비를 해준다.

정답을 쌓을 stack을 만들고 기본 로직은 인덱스를 순회할 때마다 숫자를 하나씩 푸시한다.

만약 stack에 마지막에 쌓인 값이 현재 for문의 인덱스에 해당하는 값보다 작다면 안되는 것이다 그래서 작다면 stack맨 마지막 값을 pop해버리며 제거된 양의 변수에 ++해준다 이 과정을 while문으로 돌린다.

 

function solution(number, k) {
  var answer = "";
  let answerStack = [0];
  let deleteCount = -1;
  for (let i = 0; i < number.length; i++) {
    while (deleteCount < k && number[i] > answerStack[answerStack.length - 1]) {
      answerStack.pop();
      deleteCount++;
    }
    if (answerStack.length < number.length - k) answerStack.push(number[i]);
  }
  answer = answerStack.join("");
  return answer;
}

 

처음에는 최대 o(N2) 시간초과 에러가 생긴다. 그래서 10,12번 테스트가 시간초과된다.

for문 내에서 제거할 숫자를 쌓지않고 바로 제거한다..

//10,12번 테스트 시간초과
function solution(number, k) {
  number = number.split("");
  let i = 0;
  let count = 0;

  while (true) {
    if (count === k) break;


    for (i = i; i < number.length; i++) {
      if (number[i] >= number[i + 1]) {
        i++;
        break;
      } else if (number[i] < number[i + 1]) {
        number.splice(i, 1);
        count++;
        i = i - 1;
        break;
      }
    }
  }
  return number.join("");
}