[Programmers]Python_큰 수 만들기

문제

 

문제 설명

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

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

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

 

제한사항

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

 

코드

def solution(number, k):
    stack = [number[0]]
    
    for n in number[1:]:
        #앞에 있는 숫자가 n 보다 작다면 큰 숫자가 될 수 없다
        while stack and stack[-1] < n and k:
            stack.pop()
            k -= 1
        stack.append(n)
    
    #예를 들어 같은 숫자가 많이 있을 경우에 어떤 숫자를 지워도 같은 크기가 되므로 남은 k만큼 슬라이싱
    if k:
        stack = stack[:-k]
        
    return ''.join(stack)

 

진행 과정

 

예제 #1

number = "1231234"

k = 3

 

간단히 생각하면 앞자리의 숫자가 뒷자리의 숫자보다 작으면 앞자리의 숫자를 지워야 큰 숫자가 나온다.

 

"12"는 뒤에 "3"보다 작은 숫자들이기때문에 지워야 큰 숫자가 된다. 여기서 2개의 숫자를 지웠다.

이후에 "1"은 뒤에 "2"보다 작은 숫자이기 때문에 지워져서 나머지 1개의 숫자가 지워졌다.

이 과정을 거치면 "3234"라는 결과가 나온다.

 

일단 앞에서부터 숫자를 두 개씩 비교해가며 진행하는데 더 큰 쪽이 stack으로 추가된다. 더 작은 쪽은 지워지고 k 값이 1만큼 줄어든다.

 

"1" < "2" : 2가 더 크므로 1 삭제, k -= 1

"2" < "3" : 3이 더 크므로 2 삭제, k -= 1

 

앞자리의 숫자가 더 크다면 지우지 않고 다음 자리의 숫자를 추가하여 똑같이 위의 과정을 진행한다. k 값이 0이 될때까지 반복하게되면 stack에는 그 동안 비교했던 숫자들 중 가장 큰 값들이 차례대로 들어가있을 것이다. k 값만큼 모두 지워져도 아직 numbers에 숫자가 남아있으면 "and k"라는 조건에 의해 계속 stack에 나머지 숫자들이 추가된다.

 

만약 numbers = "1111111" 과 같이 모든 숫자가 같으면 어떤 숫자를 지워도 똑같은 크기의 숫자가 된다. 그러므로 stack[:-k]으로 슬라이싱한 값, 뒤에 k만큼의 숫자를 버린 값이 정답이 된다. [:k + 1]도 정답처리가 되던데... 반례를 찾기 귀찮으니 각자 알아서 생각해보자.

 

코드 진행은 다음과 같다.

 

1) stack = ['1']

2) n = 2
3) stack = ['2'] #'1'이 더 작으므로 삭제 후 '2'추가

4) n = 3

5) stack = ['3'] #'2'가 더 작으므로 삭제 후 '3'추가

6) n = 1
7) stack = ['3', '1']

8) n = 2
9) stack = ['3', '2']

10) n = 3
11) stack = ['3', '2', '3']

12) n = 4
13) stack = ['3', '2', '3', '4']

 

14) return '3234'