문제 설명
어떤 숫자에서 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" |
내 풀이
def solution(number, k): result = [] to_remove = k for n in number: while result and n > result[-1] and to_remove > 0: result.pop() to_remove -= 1 result.append(n) if to_remove != 0: return ''.join(result[:-to_remove]) else: return ''.join(result)
정확성 테스트: ~86.92ms / 13.6MB
result를 스택으로써 조건에 맞는 수는 넣고 아닌 수는 넣을 것이다.
for문을 통해 number내의 n을 탐색한다.
만약에 result의 맨 뒤 숫자가 n보다 작다면 result에서 pop하고 숫자를 하나 지웠으니 to_remove에서 1을 뺀다.
만약에 빼고 나서도 result의 맨 뒤 숫자가 작다면 또 빼야 하므로 아예 while문으로 반복시켜 준다.
to_remove가 양수일 때, 즉 제거가 가능한 한 while에서 루프를 돈다.
pop의 여부와 관계없이 n은 결과적으로 result에 append 해준다.
for문을 벗어났는데도 불구하고 to_remove가 양수라면 result를 [:-to_remove]로 슬라이싱하여 join한 뒤에 return하고, 아니면 그냥 result를 join하여 return한다.
itertools 모듈의 combinations 함수를 사용하면 쉽게 풀 수 있는 문제지만 효율이 극도로 떨어지므로 위와 같이 풀어야 런타임을 줄일 수 있다.
