<Level 2> 큰 수 만들기 with JS

문제 설명

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

 

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

 

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

 

제한 조건

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

 

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

 

- 그리디 유형으로 분류된 문제이다. 처음에는 조합으로 풀어야하나라는 생각을 했지만 제한조건이 number가 1,000,000 이하가 아니라 1,000,000 "자리" 이하 라는 것을 보고 조합은 포기했다.

 

- 조합을 포기하고 그리디로 생각을 하게되니 조금 방향이 보였다. 숫자가 최대가 되려면 앞자릿수는 클수록 좋다. 그렇게 방향을 잡고 세번째 예시인 4177252841을 보자. 

 

 - 첫째자리부터 시작해서 4 1 7 7 순으로 기록하게 되는데, 1을 확인했을 경우 이미 앞자리에 있는 4보다 작으므로 4는 유지되어야 한다. 하지만 7을 보게될 경우 7은 당연히 앞에 와야 좋으며 앞에 있는 1보다 크다. 총 4번을 뺄 수 있으므로 먼저 1을 뺀다. 이제 3번 남았고, 앞에 있는 4보다 7은 또 크다. 그래서 4도 빼고 7을 기록한다. 이제 남은 횟수는 2이다. 

 

 - 위를 반복하면 남은 횟수가 0이 되고, 그 때부터는 남은 숫자를 모두 기록하면 된다. 이를 코드로 구현하는 것이 조금 머리가 아팠다. while을 활용해서 위를 만들었고, answer.join("")으로 제출했다. 그러나 하나의 히든케이스에서 오답판정을 받았다.

 

 -  그래서 반례를 생각해보았다. "777" k=1 이 내가 생각한 반례이다. 이 경우 7보다 작은 수는 없으므로 뺄 횟수가 남아있음에도 push만 일어난다. 즉 777을 반환하는 것이다. 그래서 마지막 return에서 자릿수를 맞추고 뒤에 들어온 숫자는 버리도록 구현하였다.

 

---

 

참고

 

코딩테스트 연습 - 큰 수 만들기