[BOJ] 2812 크게 만들기 (Python3)

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

예제 입력 1
4 2
1924

예제 출력 1
94

예제 입력 2
7 3
1231234

예제 출력 2
3234

예제 입력 3
10 4
4177252841

예제 출력 3
775841

코드

n, k = map(int, input().split())
numberList = list(input())
stack = []
answer = []
K = k
for num in numberList:
    while stack and stack[-1] < num and k >0:
        stack.pop()
        k -= 1
    stack.append(num)
        
print(''.join(stack[:n-K]))

10 4
9876543210
987654

문제 풀이

크기를 비교해서 처리하는 문제이므로 스택을 사용해서 푼다.

1) N자리 숫자를 리스트에 넣은 뒤 하나씩 for문으로 불러와서 stack[-1]이 num보다 작으면 stack.pop()해준다. 숫자를 하나 제거했으므로 제거해야할 숫자의 개수인 k를 -1 해주어야 한다.

2) 만약 stack이 비어있으면 해당 숫자를 append()해주어 stack을 채워준다.

두가지를 반복하다가 만약 k가 0이되면 삭제할 수 있는 횟수를 모두 소진한 것 이므로, 남은 숫자를 모두 stack에 넣어준뒤 n-K만큼 잘라 출력해주면 된다.