Step 4: 탐욕법(Greedy) 대표 문제 풀이: 큰 수 만들기

강의

탐욕법을 사용할 때에는 탐욕법을 사용하여도 그 뒤에 일어날 일에서도 최적의 해를 갖는지 확인해야 합니다.

 

 

 

Step 4-3: 풀어서 내 것으로 만들자! 큰 수 만들기

⭐ 이전에 풀었던 문제!

def solution(number, k):
    stack = []
    
    cnt = 0

    for num in number:
        while stack and stack[-1] < num and cnt < k:
            stack.pop()
            cnt += 1

        stack.append(num)  
        
    while cnt < k:
        stack.pop()
        cnt += 1

    return ''.join(stack)

⭐ 힌트 풀이 : 앞에서부터 삭제한 경우 자연스럽게 내림차순이 되는 점을 이용하는 방법!

def solution(number, k):  
    collected = []
    
    for i, num in enumerate(number):    # index, value 동시 추출
        while len(collected) > 0 and collected[-1] < num and k > 0:
            collected.pop()
            k -= 1
            
        if k == 0:
            collected += list(number[i:])
            break
            
        collected.append(num)
        
    collected = collected[:-k] if k > 0 else collected
    
    return "".join(collected)