[프그] 그리디 : 큰 수 만들기 ★

문제

아이디어

바로 떠올리기 어려운 해법이다ㅠ
두 개의 리스트를 활용한다.
제거해야할 개수(k)를 낮춰주고, 두 리스트사이에 맞닿아있는 숫자를 비교하면서
뒤에서 앞으로 숫자를 보내주는 방식으로 처리한다.

answer: []              number: 1231234 k: 3
answer: ['1']           number: 231234  k: 3
answer: ['2']           number: 31234   k: 2
answer: ['3']           number: 1234    k: 1
answer: ['3', '1']      number: 234     k: 1
answer: ['3', '2']      number: 34      k: 0
answer: ['3', '2', '3'] number: 4       k: 0
>> ['3', '2', '3', '4']

코드(성공)

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

응용

• 만약 k개의 수만 선택하는 문제라면 len(numbers) - k의 값이 제거해야할 개수이니, 똑같이 풀 수 있겠다.