[프로그래머스] 큰 수 만들기/Python - Lv.2

❓문제

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

성능 요약

메모리: 14.7 MB, 시간: 129.68 ms

구분

Greedy

문제 설명

어떤 숫자에서 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개만큼 제거해서 가장 큰 수를 만들어야 한다. 가장 큰 수를 만들어야 한다는 것은 첫 번째 숫자가 크면 된다.

4177252841을 예로 생각해보자. 4개를 모두 제거하였을 때 남은 숫자의 수는 6개이다. 이 때, 맨 앞에 올 수 있는 가장 큰 수는 7이 된다.
그렇다면 우리는 4와 1을 제거해야 한다는 것을 알 수 있다.

4와 1을 제거하고 k를 감소시킨다. 그러면 7이 맨 앞 자리 숫자가 된다. 위와 마찬가지로 진행하면

7과 2를 지나 5가 있다. 우리는 아직 숫자를 제거할 수 있고 5가 2보다 더 크므로 큰 수를 만들기 위해 2를 제거해야 한다.
그러므로 2를 제거하고 k를 1 감소하면 된다.

나머지도 마찬가지로 하면 결국 남는 숫자는 75841이 된다.

그런데 위와 같은 방식은 큰 숫자가 나오면 작은 숫자들을 지우는 방식이다. 그렇다면 만약 뒤에 있는 숫자들이 다 작아서 지워지지 않는 경우도 있을 것이다. 예를 들어, 10이 주어진다면 이 때 k = 1로 1개를 제거해야 한다. 그렇다면 우리는 남은 개수만큼 뒷부분에서 제거하면 된다. 그러면 만들 수 있는 큰 수는 1이 된다.

💻코드

def solution(number, k):
    answer = ''
    num = []
    for n in number:
        while len(num) > 0 and num[-1] < n and k > 0:
            num.pop()
            k -= 1
        num.append(n)
    
    return answer.join(num[:len(number)-k]) # 남은 k만큼 뒷부분에서 제거.

📍후기

수학 공부를 어떻게 했었지라는 생각으로 다시 공부하려니까 어떻게 공부해야 할지 감이 잡히는 느낌이다.