💡 스택, 그리디를 활용해 풀이, 프로그래머스 3단계

문제 🛫

---

큰 수 만들기

문제 참조 : https://programmers.co.kr/learn/courses/30/lessons/42883

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

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

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

제한 조건
number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.

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

분석

스택, 그리디를 활용해서 풀 수 있다.

• 스택을 만든다. 배열 item을 순차대로 넣는다.
• 높은 자리의 숫자가 다음 자리 숫자보다 작으면 pop해서 없앤다. (반복)
• [9,8,7,6,5,4,3,2,1] 과 같은 케이스에서 pop이 한번도 안되면서 수행이 안되는 엣지 케이스가 있다.
• 마지막에 count가 k보다 여전히 작으면 stack의 윗 부분을 pop해준다.

풀이 📖

---

Solution

function solution(number, k) {
    const stack = [];
    let count = 0;
    
    for(let item of number){
        while(count < k && stack[stack.length - 1] < item){
            stack.pop();
            count++;
        }
        stack.push(item);
    }
    
    while(count < k){
        stack.pop();
        count++;
    }
    
    return stack.join("");
}

---

Review 💡

그리디 알고리즘

• 자료구조의 선택이 중요
• 숫자를 뽑아내는 알고리즘을 생각해내는게 중요하다(구현이 중요하다).