프로그래머스 - 큰 수 만들기

문제 설명

문자열이 주어졌을 때 k개에 해당하는 문자를 지우고, 가장 큰 수를 출력하는 문제다.

접근 방식

• 모든 경우의 수를 고려하기 위해 itertools의 combinations을 이용했지만, number가 100만자리까지 나와서, 시간초과가 발생했다.
  
  
• 정답을 찾지 못하던 중, stack을 이용해 정답 배열에 들어갈 수가 정답 배열 마지막 수보다 큰 경우 바꿔주는 식으로 하는 코드를 참고할 수 있었다.
  
  

틀린 코드

from itertools import combinations
def solution(number, k):
    answer=''
    
    number = list(number)
    max_num = []
    
    for i in combinations(number, len(number)-k):
        max_num.append(i)
    
    print(max(max_num))
    
    for i in max(max_num):
        answer += i
        
    return answer

위와 같이 작성한 코드에서, 모든 경우의 수를 고려해서인지 시간 초과로 문제를 해결하지 못했다.

작성한 코드

def soulution(number, k):
    stack = []

    for n in number:
        while stack and stack[-1] < n and  k > 0:
            stack.pop()
            k-=1
        stack.append(n)

    if k > 0:
        stack = stack[:-k]
    
    answer = "".join(stack)
    return answer