[프로그래머스/파이썬] 큰 수 만들기

 

문제 설명

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

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

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

 

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

 

 

 

 

 

문제의 숨겨진(?) 요구사항은 숫자의 순서를 유지하면서 K개의 숫자를 제거했을 때 얻을 수 있는 가장 큰 수를 구해야합니다.

뒤에 오는 숫자가 앞에 오는 숫자보다 클 경우에 앞에 오는 숫자를 제거하면 순서를 지키며 가장 큰 수를 만들 수 있습니다.

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

현재 while 문의 조건은 k가 0보다 크다면 조건이 포함되어있는데, 987654와 같이 숫자가 내림차순인 경우, while문 안에 존재하는 코드들이 실행되지 않으면서 k개의 숫자를 제거하지 못하게됩니다.

따라서 마지막에 가장 작은 k개의 숫자를 뒤에서부터 제거해줌으로써 가장 큰 수를 만들 수 있습니다.