문제
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 1924에서 두 수를 제거하면 [19, 12, 14, 92, 94, 24]를 만들 수 있습니다.
이 중 가장 큰 수는 94
문자열 형식으로 숫자 number와 제거할 수의 개수 k개 solution함수의 매개변수로 주어짐
number에서 k개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요
[제한조건]
number는 1자리 이상, 1,000,000 이하인 숫자
k는 1이상, number의 자릿수 미만인 자연수
<탐욕법>을 사용할 수 있는 문제이기 때문에
앞 단계에서의 선택이 이후 단계에서의 동작에 의한 해의 최적성에 영향을 주지 않음
풀이법
가능한 수를 다 나열해서 비교하는 방법도 있겠지만, 숫자 자리수가 너무 많아지면 경우가 너무 많아질 것이다.
앞자리가 커야 수가 커진다
큰수부터 앞자리에 담고싶다
기본 보기
Search
앞자리가 커야하기 때문에 앞에 있는 작은 수들을 없애야한다.
순차적인 알고리즘으로 해결하려면 어떻게 해야할까요?
앞에서부터 담다가 담은 숫자들보다 큰 걸 마주치면 다시 뺀다
4 1 7 7 2 5 2 8 4 1, k=4
4 1 담기
4 1 7 ! 1<7, 4<7 → 4, 1뺀다. 그리고 2개 뺐다는 것을 기록해준다
7 7 2 5 → 2 < 5 → 2 뺀다 7 7 5 → 7 > 5 이므로 5는 안 뺌. 지금까지 3개 뺐다
7 7 5 2 8 → 2 < 8 → 2 뺀다 4개 다 뺐음! 더이상 뺄 수 없다.
남은 수 4, 1, 까지 붙여주면 7 7 5 2 8 4 1
정답이 나온다.
주의9 8 7 6 5 , k=2같은 경우 ( 벌써 내림차순으로 정렬이 되어있음)
9 8 7 6 5 → 앞에서 그대로 하면 빠지지가 않는다. 이 경우에는 뒤에꺼 두개를 떼어준다
정리
1.
주어진 숫자로부터 하나씩 꺼내어 모으지만
2.
이미 모아둔 것 중 지금 등장한 것보다 작은 것들은 뺀다
3.
k개만큼 다 빠졌다면 끝내고 뒤에 남은 것들을 빼준다.
4.
k개만큼 다 안빠졌다면 맨 끝에서부터 빼준다.
앞에서부터 비교하는 방법이므로 정도의 알고리즘이 나올 것
구현
def solution(number, k):
collected = [] # 담는 숫자 저장 문자열은 immutable(불변) 하기 때문에 list로 만들어준다
for i, num in enumerate(number):
while len(collected) > 0 and collected[-1] < num and k > 0:
# ascii code에서 한자리 숫자 문자는 대소관계가 같으므로 문자열 그대로 비교해도 된다.
collected.pop()
k -= 1
if k == 0:
collected += list(number[i:])
break
collected.append(num)
collected = collected[:-k] if k > 0 else collected
answer = ''.join(collected)
return answer
Python
복사
number에서 하나씩 꺼내서 추가 / 제거 하는 과정을 거치기 때문에 O(n)의 알고리즘이 된다.
