Programmers - 큰 수 만들기[파이썬(python)]

문제 출처 : 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는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

입출력 예

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

 

---

문제 풀이

이 문제는 그리디 알고리즘 문제로 분류 되어있다.

주어진 숫자에서 k개의 수를 지워 가장 큰 수를 만들어야 한다면 앞자리를 최대한 크게 만들어야 한다는 것을 생각할 수 있다.

즉 k의 제한 개수가 허락하는 한 앞에 위치한 수가 뒤에 위치한 수보다 항상 커야 한다.

Greedy 알고리즘의 관점에서 접근해보면 stack을 이용하여 문제를 해결할 수 있고 알고리즘은 다음과 같다.

 

1. number를 처음부터 순회하며 stack에 추가한다.
2. 만약 stack에 추가되어있는 수(앞자리 수)가 그다음 수(뒷자리 수) 보다 작다면 stack에서 pop 한다.
3. 제거 가능 횟수 k를 1 감소시킨다.
4. stack이 비거나 stack에 추가되어 있는 수가 그다음수보다 큰수가 될때까지 2, 3 과정을 반복한다.
5. 그 다음 수를 stack에 push 한다.
6. number의 모든 수를 순회할 때까지 2~5의 과정을 반복한다.

이해를 돕기 위해 number = "1924", k=2인 경우로 과정을 살펴보자.

 

step 0.

stack을 비어있는 배열로 초기화한다.

stack = [ ], k = 2

 

step 1.

number의 첫 번째 수인 1을 확인한다. stack이 비어있는 상태이므로 1을 stack에 추가한다.

stack = [ 1 ], k = 2

 

step 2. 

number의 두 번째 수인 9를 확인한다. stack에 추가되어있는 1은 9보다 작으므로 앞 자릿수를 크게 만들어 주기 위해 1을 stack에서 pop 하고 9를 push 한다. 이후 k를 1 감소시킨다.

stack = [ 9 ], k = 1

 

step 3.

number의 세 번째 수인 2를 확인한다. stack에 추가되어있는 9는 2보다 크므로 2를 stack에 추가한다.

stack = [ 9, 2 ], k = 1

 

step 4.

number의 네 번째 수인 4를 확인한다. stack에 추가되어있는 2는 4보다 작으므로 앞자리 수를 크게 만들어 주기 위해 2를 stack에서 pop 한다. 그다음 stack에 추가되어있는 9는 4보다 큰 수이므로 4를 stack에 추가한다. 이후 k를 1 감소시킨다.

stack = [ 9, 4 ], k = 0

 

위 과정이 끝났다면 stack에 있는 수를 문자열로 변경하면 된다. 여기서 주의할 점은 number가 내림차순 형태로 주어진 경우에는 어떠한 수도 지워지지 않고 전부 stack에 추가된다. 이러한 경우는 stack의 뒤에서부터 k번째까지를 제외하면 된다.

구현 코드

코드 링크 : 큰 수 만들기

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