프로그래머스 고득점kit 큰 수 만들기 | Python

🔎 문제 설명

💚 Level 2

- 난이도 ★★☆☆
- 그리디 (LIFO)

LIFO 방식을 이용하여 코드를 작성하였다. 앞에서부터 수를 스택에 넣어주고 이전에 마지막으로 넣은 값 stack[-1] 보다 큰 값을 만나면 stack[-1] 를 빼준다.

stack.pop()

이걸 k 번 반복해주면 된다. 밑에 코드를 첨부해놓았다.

그리디 알고리즘이란

매 선택에서 지금 이 순간이 당장 최적인 답을 선택하여 적합한 결과를 도출하자

그 순간에 대해서는 최적이지만 종합적으로 봤을 때는 최적이라는 보장이 없다는 단점이 있다. 그래서 그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다. 즉, 이번 문제는 그리디로 푸는 것이 적합하다!

💻 내 코드

def solution(number, k):
    stack = []
    out_len = len(number) - k
    for num in number:
        while stack and k > 0 and stack[-1] < num:
            stack.pop()
            k -= 1
        stack.append(num)
    return ''.join(stack[:out_len])