[Programmers]큰 수 만들기

문제

출처 : 프로그래머스 큰 수 만들기

 > 문제 링크 

프로그래머스

---

문제 풀이

 해당 문제는 탐욕범을 사용하여 풀 수 있다. 숫자를 제거하며 높은 자리 부터 탐욕적으로 채워나가면 된다.

 

주어지는 number의 첫 자리부터 시작하여 비어있는 stack에 하나씩 psuh해준다. push를 하기 전 저장된 stack의 top의 값과 비교한다. 이 때 top보다 현재 자리의 숫자가 크다면 해당 top을 pop해준다. 이렇게 pop된 숫자는 제거가 된 숫자이다. 그렇기에 제거가 될 때 k를 -1 해준다.

 

해당 과정을 반복하여 k가 0이 되면 해당 과정을 멈추고 stack과 비교 전인 number의 뒷 자리를 더하여 출력해준다.

 

과정 1

과정 2

과정 3

 

과정 4

그림 출처

---

코드

function solution(number, k) {
     const answer = [];
  for (let num of number) {
    while (k > 0 && answer[answer.length - 1] < num) {
      answer.pop(num);
      k -= 1;
    }
    answer.push(num);
  }
  return answer.join("").slice(0, number.length - k);
}

 

---