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

1. 문제 설명

 

 

 

2. 제한 조건

 

 

 

3. 입출력 예 

 

 

4. 나의 풀이

 쉽게 생각했다가 큰 코 다친 문제다. 예상치 못했던 테스트 케이스 10에서의 시간 초과는 멘붕 그 자체였다. 그런데 이 문제가 탐욕법이라는 범주안에 있는 것을 생각해보면, 이 문제는 정말 탐욕법스러운 문제라 할 수 있을 것 같다. 이제 풀이를 시작하도록 하겠다.

 

 

 이 문제가 물어보는 메세지를 파악하는 것이 중요하다. 이 문제의 메세지는

 

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

 

 이다. 테스트 케이스 10(시간 초과)을 해결할 수 있었던 것은 내가 짰던 코드의 방향을 아예 바꾸는 것이었다(다른 블로그(참고 자료 출처)를 참고했다). 기존에 풀던 방식은 투 포인터를 이용하는 것이었다.

 

[그림 1] 투 포인터

 

 방법은 다음과 같다.

1. 입력: "1924", k: 2를 받는다.
2. 입력 배열 길이 - k가 2가 된다. "1924"에서 숫자 두 개를 없애서 가장 큰 수 2자리를 만들어야 한다.
3. 만들어야하는 가장 큰 수는 2자리 이므로 , 끝에서 1자리를 제외한 원소들 중 최대 값을 찾는다.
4. 최대 값 9를 찾았다. answer에 9를 대입하자.
5. 최대 값 9의 인덱스는 1이다. 인덱스 1 이 후부터 끝까지 범위에서 최대값을 찾는다.
6. 최대값 4를 찾았다. 
7. anwer에 4를 대입하자.
8. 정답은 94

 하지만 이 방법은 테스트 10(시간초과)를 제외한 모든 경우에서만 잘 된다. 따라서 통과를 못한다. 참고 자료를 참조한 블로그에서는 다음과 같이 풀었다. 

 

 

스택을 이용한 방법

 

 1. 스택의 길이가 0이므로, 입력 배열의 첫 요소를 스택에 삽입한다(k=2).

 

[그림 2] 1 단계

 

 2. 이번 요소의 값은 9, 스택의 길이는 1이며 스택에 있는 값은 1이다. 1과 이번 요소 9를 대소여부를 비교한다. 9가 더 크므로 스택에서 1을 빼고, k 값을 1 감소시킨다. 그리고 스택에 남아있는 값이 있는지 확인한다. 남아있는 값이 없으므로 9를 스택에 삽입한다.

 

[그림 3] 2 단계

 

 3. 이번 요소 값은 2다. 2는 스택에 있는 9보다 값이 작으므로, 스택에 2를 집어넣는다.

 

[그림 4] 3 단계

 

 4. 이번 요소 값은 4다. 4는 2보다 크다. 따라서 스택에 있는 2를 꺼낸다. k를 1 감소시키고 스택에 4를 넣는다. k의 값이 0이 되므로 더 이상 뺄 숫자가 없다. 

 

[그림 5] 4 단계

 

 5. k가 0일 때 스택 값 자체를 문자열로 만들면 답이된다. 그런데 k > 0일 경우, 스택 끝에 k번째 값만 없애주고 문자열로 만들어주면 된다. 따라서 이번 경우는 k가 0이므로, 답은 94가 된다.

 

 

프로그래밍 코드는 다음과 같다.

function solution(number, k) {
  const stack = [];
  let answer = '';

  for(let i=0; i<number.length; i++){
    const el = number[i];

    while(k > 0 && stack[stack.length-1] < el){
      stack.pop();
      k--;
    }

    stack.push(el);
  }

  stack.splice(stack.length-k, k);
  answer = stack.join("");
  return answer;
}

 

 

5. 참고 자료

 프로그래머스 - 큰 수 만들기(javascript), kimtaeeeny.log