문제
강의에 들어있는 문제라서 문제 링크를 걸어도 되는지 모르겠다.
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 수 구하기
숫자 : number
제거할 개수 : k
number는 1자리 이상 1,000,000자리 이하인 숫자
k는 1이상 number의 자릿수 미만인 자연수
입출력 예시
| number | k | return |
|---|---|---|
| “1924” | 2 | “94” |
접근
탐욕법을 이용하여 풀 수 있다.
앞자리에 큰 숫자가 나올수록 전체 수의 크기는 커질 것이다.
이를 이용하여 앞자리부터 한글자씩 비교하며 큰수를 담고, 작은 수는 버리는 방법을 사용하면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(number, k):
collect = []
for i, num in enumerate(number):
while k > 0 and len(collect) > 0 and num > collect[-1]:
collect.pop()
k -= 1
if k == 0:
collect += list(number[i:])
break
collect.append(num)
collect = collect[:-k] if k > 0 else collect
answer = ''.join(collect)
return answer