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

후... 이번엔 정말 무기력감을 느꼈던 문제였다. 풀다가 도저히 안 되서 다른 사람들의 풀이를 보고 말았는데, 내가 생각해낸 건 절반도 채 안되는 것 같아서...

접근 방법

접근 방법은 다음과 같다.

1. 순서대로 하나씩 빼주면서 가장 큰 수를 만들어야 한다.
2. 가장 min 수 k개 빼준다? NO! 772141에서 앞의 1과 뒤의 1은 같은 1이지만 다른 자릿수를 가져서 다른 의미이다.
3. Greedy하게 순간 순간 최선의 판단을 내리기 위해 내 이전 수가 작으면 내쫓고 대신 들어간다고 생각하자.
4. 내 이전 수들은 어디에 보관?? Stack이 가장 바람직할 것 같다.

풀이

function solution(number, k) {
    
    // 큰 수를 만들어야 한다. 
    // Greedy : 그 때 그 때 최선의 판단을 내려서.
    // 그 때 최선의 판단이란..?? 가능할 때 까지 내 앞의 작은 수들을 치워버리는 것.
    let answer = '';
       
    let stack = []; // 내 앞의 수들을 보관할 스택
    for(let i = 0; i < number.length; i++){
        let cur = number[i] // 현재 숫자
        // 나보다 작은 친구들 치워버리기. 
        //가장 최근 녀석이 stack[stack.length-1]
        while(k > 0 && stack[stack.length - 1] < cur){
            stack.pop(); // cur보다 작은 것 버리기 ... 반복!
            k--;
        }
        stack.push(cur); 
      	// 앞의 나보다 작은 녀석들을 모조리 치워버렸으면 push
    }
    
    answer = stack.join('');
    
    // 만약 숫자가 계속 작아지는 수인 경우 k가 남겠지.? 54321, k= 2
    // 이런경우는 그냥 뒤에서부터 k개 잘라
    
    if(k > 0){
        answer = number.slice(0,number.length-k)
    }
    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/42883#