[Python] 탐욕법(Greedy) | 큰 수 만들기

인증사진(2024-11-10)

문제

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

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

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

 

답

def solution(number, k):
    stack = []
    
    # enumerate를 이용해 숫자와 인덱스를 함께 다룬다.
    for i, num in enumerate(number):
        # 현재 숫자가 스택의 마지막 숫자보다 크고, 제거할 수 있는 기회가 남아 있는 경우
        while k > 0 and stack and stack[-1] < num:
            stack.pop()  # 스택의 마지막 숫자를 제거
            k -= 1       # 제거 기회를 하나 줄임
            
        stack.append(num)  # 현재 숫자를 스택에 추가
        
    # 만약 k가 남아 있다면 뒤에서부터 제거
    if k > 0:
        stack = stack[:-k]
        
    # 스택을 문자열로 변환하여 결과 반환
    return ''.join(stack)

 

추가공부

enumerate(number) 쓰면 편하네. 스택의 마지막 값이 num보다 작으면 제거하고, 제거할 기회가 남아 있는 경우에만 수행하게 하는 것.
모든 숫자를 순회한 후, 만약 k가 남아 있으면, stack의 뒤에서 k개를 잘라내어 최종 결과를 만듦