[백준 2812번] 크게 만들기

2812번: 크게 만들기

n, k = map(int,input().split())

number = list(input())

stack = []

for i in range(n): 
    while stack and number[i] > stack[-1] and k > 0: 
        # 현재 숫자가 stack에 있는 숫자보다 크면 stack.pop()
        # 가장 큰 숫자를 앞 쪽에 위치시키기 위함 !
        # k개 까지만 지워야 하므로 k > 0이상일 때만 수행
        stack.pop() 
        k -= 1
    stack.append(number[i])

# 만일 k개 미만으로 숫자를 지웠다면 뒤에 있는 숫자를 남은 k개 만큼 지우고 출력한다.
if k > 0:
    print(int("".join(stack[:-k])))
else:
    print(int("".join(stack)))

이번 문제는 주어진 N자리 숫자에서 k개를 지워서 만들 수 있는 가장 큰 수를 구하는 문제이다.

 

처음에 DFS로 풀이하였지만 메모리 초과가 발생하여 다른 사람의 풀이를 참고해본 결과, 스택 자료구조를 사용해서 첫번째 숫자부터 스택에 담고나서 앞 쪽에 가장 큰 수를 위치시키기 위해(Greedy) k번 pop 해주며 가장 큰 수를 유지해주는 방식으로 풀이할 수 있었다.

 

그리고 주의할 점은 k번 pop해주지 않았을 경우가 있기 때문에, 이 경우에는 마지막 부분에서 남은 k만큼 지워주면 된다.