[프로그래머스/Python] 큰 수 만들기(그리디)

코딩테스트 연습 - 큰 수 만들기

k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구해야한다.

 

1) 부르트 포스

 

당장 생각해볼 수 있는 방법은 k개의 수를 임의로 제거한 모든 경우의 수를 계산하고 그 중 가장 큰 수를 출력하는 것이다. 문제를 곧이곧대로 해석. 하지만 아래와 같이 풀면 시간초과가 난다. 그도 그럴 것이 number가 1,000,000자리까지 가질 수 있다. 

 

from itertools import combinations
def solution(number, k):
    answer = ''
    number = list(map(''.join, combinations(number, len(number)-k)))
    return max(number)

 

 

2) 그리디 알고리즘

 

스택을 이용해 실시간으로 처리

 

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