[프로그래머스] 큰 수 만들기 (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의 자릿수 미만인 자연수입니다.

입출력 예

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

문제풀이

KeyPoint

1. return할 array에 첫 번째 숫자를 미리 넣어둔다. 이게 기준점이 되도록.
2. array에 새로운 숫자를 넣기 이전에 array에 있는 element가 새로운 수보다 작다면 기존의 element를 제거한다. k가 0이 될 때까지 대소비교를 반복한다.
3. 기존 element 제거 후, 새로운 숫자는 일단 무조건 배열에 넣는다. 제거해야할 숫자는 나중에 2번 과정을 통해서 알아서 제거될 것.
4. 만약 끝까지 k가 0이 되지 않았을 경우,
   (ex. number="1000", k=1 일 경우 return 할 배열은 [1,0,0,0]이 됨)
   마지막 k자리를 잘라냄.

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

문제 풀러 가기!👇

큰 수 만들기