프로그래머스 - Lv2. 큰 수 만들기

관련 자료구조/알고리즘 : 탐욕법

문제 설명

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

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

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

제한 조건

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

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

출처

https://hsin.hr/coci/archive/2011_2012/contest4_tasks.pdf

풀이

const solution = (number, k) => {
//     1. stack 준비
    const stack = [];
    
//     2. 인자로 들어온 string을 number의 배열로
    const arr = number.split('').map(v => Number(v));
    
//     3. 카운트 초기화
    let cnt = 0;
    
//     4. 배열을 순회
    for(let i = 0; i < arr.length; i++) {
        
//     5. 스택이 비어있으면 현재 값을 push하고 다음 값부터 탐색
        if(stack.length === 0) {
            stack.push(arr[i]);
            continue;
        } 
        
//      6. 스택이 비어있지 않고, 스택의 마지막 값이 순회 중인 배열의 값보다 작으면
//         스택의 마지막 element를 제거하고, 카운트를 1 증가시켜 줌.
        while(stack.length && stack[stack.length - 1] < arr[i]) {
            stack.pop();
            cnt++;
            
//      7. 카운트가 k(제거해야 하는 숫자의 개수)가 되면 while 루프에서 빠져나옴.
            if(cnt === k) break;
        }
        
//      8. 스택의 마지막 값이 순회중인 배열의 값보다 크면 현재값을 스택에 push
        stack.push(arr[i]);
        
//      9. 종료 조건 (아직 순회하지 못한 부분은 이어 붙임)
        if(cnt === k) return stack.join('') + number.substr(i + 1)
    }
//     10. 예외 처리 (배열을 다 순회해도 카운트가 k값에 도달하지 못할 때)
    return stack.join('').slice(0, number.length - k + cnt)
}