문제

https://programmers.co.kr/learn/courses/30/lessons/42883

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

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

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

제한 사항

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

입출력 예시

아이디어

👎 맨 처음 들었던 생각은 전체 길이에서 k만큼 제거하니까 (전체길이 - k)만큼 반복하면서 가장 큰 숫자를 뽑아서 인덱스 순으로 정렬하면 된다고 생각했다.
하지만, 이 방식으로 하면 다음과 같은 문제가 생긴다.

자릿수를 고려하지 않고 max값만 가져왔기 때문에 맨 앞자리가 7이 아닌 4가 되는 것이다.

[#Error] solution함수_python

def solution(number, k):
    answer = ''
    new_number = []
    number = list(map(int, number))
    num = len(number) - k
    for i in range(num):
        max_num = max(number)
        max_idx = number.index(max_num)
        number[max_idx] = 0
        new_number.append([max_idx, max_num])
    new_number.sort(key = lambda x : (x[0]))

    return answer

[#Error] solution함수_python

:: 시간초과

모든 조합을 구하여 가장 큰 수를 출력한다. 하지만 너무 오래 걸린다.

import itertools

def solution(number, k):
    number = list(map(int, number))
    num = len(number) - k
    new_number = list(map(list,itertools.combinations(number, num)))
    new_number.sort(reverse = True)
    return ''.join(map(str, new_number[0]))

Clone 코드 아이디어

✅
1. stack을 만들어서 number에 있는 수를 하나씩 넣는다.
2. num이 stack의 마지막 수보다 작으면 넣는다.
3. num이 더 크면 k가 0보다 클 때까지 하나씩 제거한다.
4. k가 0이 되거나(주어진 수만큼 다 제거한 경우), num의 모든 수가 stack에 들어간 경우 종료한다.
5. 마지막에 k가 0 이상인 경우 k만큼 뒤를 잘라준다.

[#Clone] solution함수_python

:: 아이디어 참고해서 작성한 코드

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

[#Clone] solution함수_python

def solution(number, k):
    answer = [] # Stack

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

    return ''.join(answer[:len(answer) - k])

clone코드 출처