[백준/BOJ] gold3 - 2812번 크게 만들기

▶2812 - 크게 만들기

백준 로고

 

▶문제

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

 

▶입력

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

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

 

▶출력

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

728x90

▶풀이

Stack을 사용하는 문제로 지난번에 풀었던 17298 - 오큰수와 거의 비슷한 문제이다.

문제풀이 방법 자체가 동일하다고 생각해도 무방하다.

2024.10.05 - [BOJ Code/Gold] - [백준/BOJ] gold4 - 17298번 오큰수

[백준/BOJ] gold4 - 17298번 오큰수

 

stack을 이용해서 좌측에 작은 수를 제거하면 된다.

k번 제거해주고 나면 큰 수들만 남게 된다.

 

그렇게 하는 이유는 제일 앞자리 수가 가장 큰 수가 되면 되기 때문이다.

마지막에 range(len(stack - k)를 하는 이유는,

반복문을 돌려도 k번만큼 제거가 되지 않는 경우가 있기 때문이다.

그렇게 되면 그냥 뒤에 숫자를 남은 k개만큼 제거하면 된다.

n, k = map(int, input().split())
num = input().rstrip()
stack = []
answer = ''

for i in range(n):
    while k > 0 and len(stack) != 0 and int(stack[-1]) < int(num[i]):
        stack.pop()
        k -= 1
    
    stack.append(num[i])

for i in range(len(stack) - k):
    answer += stack[i]

print(answer)