[프로그래머스|파이썬] 큰 수 만들기 (탐욕법(Greedy)/lv.2)

문제

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

프로그래머스

 

 

🐍파이썬

def solution(number, k):
    answer = ''
    idx = number.index(max(number[:k]))
    k -= idx
    number = number[idx:]   #k개 중 가장 큰 수까지 앞부분 자르기
    for i in range(1, len(number)-k):
        if k == 0:
            break
        if number[i] < number[i+1]:
            number = number[:i]+number[i+1:]
            k -= 1
    return number

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

가장 큰 수를 만들기 위해서는, 큰 수가 앞자리에 존재하도록 해야 한다.

1️⃣ number의 숫자를 한글자씩 순회하며 현재 숫자(i)가 스택의 마지막 숫자(stack[-1])보다 작은지 확인한다. 현재 숫자가 스택의 마지막 수보다 크다면 앞자릿수(stack[-1])를 없애야 가장 큰 수가 되기 때문에, 앞자릿수를 없앤다(stack.pop()).

ex) number = "1924"

👉 i = "9", stack = ["1"]일때,

i(=9)는 stack[-1](=1)보다 크기 때문에 stack[-1]의 값을 지우고 i를 스택에 추가한다.

2️⃣ 매번 k값을 빼주어 앞으로 삭제해야 할 수의 갯수를 업데이트 해준다.(k -= 1)

3️⃣ number의 모든 수를 순회했는데도 k가 0 이상인 경우를 처리하기 위해 stack 가장 뒤의 숫자 k개를 삭제한다. 코드 상에서는 stack의 0번 인덱스부터 len(stack)-k-1인덱스까지 슬라이싱함으로써 이를 구현했다. (stack[:len(stack)-k])