Programmers Lv.2 큰 수 만들기

📚 문제 설명

어떤 숫자에서 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"

📖 문제 풀이

Code_1 - 실행 에러

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

• 제한 조건이 100만 자리 이하의 자연수이므로 시간 초과가 날 것을 예상하긴 했지만 조합을 이용한 단순한 방법이므로 구현해봄

Code_2 - 성공

def solution(number, k):
    answer = []
    for n in number:
        if len(answer) == 0:
            answer.append(n)
            continue
        if k > 0:
            while answer[-1] < n:
                answer.pop()
                k -= 1
                if len(answer) == 0 or k <= 0:
                    break
        answer.append(n)
    answer = answer[:-k] if k > 0 else answer
    return ''.join(answer)

• 스택에 담긴 마지막 값이 새롭게 넣을 값보다 작다면 크거나 같은 수가 나올 때까지 pop함