알고리즘/백준
스택 : 크게 만들기(백준 2812번)
bewisesh91
2021. 11. 17. 23:50
728x90
▶ 문제 : https://www.acmicpc.net/problem/2812
2812번: 크게 만들기
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
##### 문제 #####
# N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
##### 입력 #####
# 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
# 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
##### 출력 #####
# 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.
▶ 접근 방법
▶ 풀이 코드
N, K = map(int, input().split())
numbers = list(input())
k, stack = K, []
for i in range(N) :
while k > 0 and stack and stack[-1] < numbers[i]:
stack.pop()
k -= 1
stack.append(numbers[i])
print(''.join(stack[:N-K]))
▶ 관련 링크
2021.11.17 - [알고리즘] - 스택(Stack)이란?
2021.11.17 - [알고리즘] - 스택 : 스택(백준 10828번)
2021.11.17 - [알고리즘] - 스택 : 제로(백준 10773번)
2021.11.17 - [알고리즘] - 스택 : 괄호(백준 9012번)
2021.11.17 - [알고리즘] - 스택 : 막대기(백준 17608번)
2021.11.17 - [알고리즘] - 스택 : 탑(백준 2493번)