[BaekJoon] 2812 크게 만들기 (Gold 3) - Python

문제

 

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

---

코드

import sys
input = sys.stdin.readline # 입력 빠르게 하기 위해 input함수 재정의
N, K = map(int, input().rstrip().split()) # N, K 입력
num = list(input().rstrip()) # 숫자 입력
stack = [] # 스택 선언
for x in num: # num의 개수만큼 반복하여
    while stack and stack[-1] < x and K > 0: # 만약 스택이 비어있지 않고, 스택의 맨 위의 원소가 현재 숫자보다 작고, 숫자 제거 기회를 전부 사용하지 않았다면
        stack.pop() # 스택의 맨 위 원소를 제거하고
        K -= 1 # 제거 기회를 1 감소하낟
    stack.append(x) # 현재 원소를 스택의 맨 위에 추가한다

if K > 0: # 만약 제거기회를 전부 사용하지 않았다면
    print(''.join(stack[:-K])) # 스택의 뒷부분에서 남은 K만큼을 제거한 뒤 출력한다
else: # 전부 사용했다면
    print(''.join(stack)) # 그냥 스택을 출력한다.

 

---

실행 화면

 

---

채점 결과