[코테] 백준 그리디 2812번 문제

2812번 : 크게 만들기

문제 링크

https://www.acmicpc.net/problem/2812

문제 설명

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

입력

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

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

출력

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

문제 풀이

풀이1 이외에도 많은 시행착오를 겪었지만 시간 초과로 모두 실패하였다.

이번 문제는 출력할 리스트를 따로 만든다는 생각을 하면 풀리는 문제이다.

아직 많이 부족하다는 것을 느끼면서 열심히 해야겠다는 생각을 한다.

# 풀이1 : 시간 초과
N, K = map(int, input().split())
num = input()
idx = 0

while K > 0 :
    if idx == len(num)-1 : 
        num = num.replace(num[num.find(min(num))], '', 1)
        idx = 0
        K -= 1
    
    elif num[idx] < num[idx+1] :
        num = num.replace(num[idx], '', 1)
        idx = 0
        K -= 1
        
    else : idx += 1
    
print(int(num))

# 풀이2 : 다른 사람들의 정답 코드
n, k = map(int, input().split())
s = input()
stack = []

for c in s:
    while stack and k > 0 and stack[-1] < c:
        stack.pop()
        k -= 1
    stack.append(c)

if k > 0 : 
    print(int("".join(stack[:-k])))
else : 
    print(int("".join(stack)))