문제 링크
문제 요약
그리디 문제 에 해당한다.주어진 숫자 문자열에서 k개의 숫자를 제거하여 얻을 수 있는 가장 큰 숫자를 구하는 문제. 문자열 형태로 주어진 숫자인 number와 제거할 숫자의 개수 k가 주어짐. 이를 활용하여 가장 큰 숫자를 만들고 그것을 문자열로 반환.
문제 풀이
def solution(number, k):
answer = []
for i in range(len(number)):
while k > 0 and answer and answer[-1] < number[i]:
# 아직 제거해야할 k의 개수가 남아 있고
# answer 배열이 안 비어있고
# answer 배열의 마지막 값이 현재 number 배열의 값보다 작다면
k-=1
answer.pop()
answer.append(number[i])
if k != 0:
answer = answer[:-1]
return ''.join(answer)
📌 고려해야할 점
- 그리디 문제 유형이다.
- 처음에는 최대값을 위해서 그냥 리스트로 변환해서 정렬하면 되는 줄 알았는데, 그게 아니었다 ㅎㅅㅎ
- 스택 자료구조를 이용해서 문제를 풀이하는데, 마지막에 k=0 이 아니라면 가장 마지막 숫자를 제거하고 정답으로 반환해줘야한다.
"654321"이 number, k=1이라면 가장 마지막 '1'만 제거해줘야하는 테케가 있음
