[BoJ] 2812 크게 만들기

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

접근법

Brute-force

1. 가능한 모든 조합을 고려하여 최댓값을 생각해본다
2. N 이 500,000 이므로 당연히 시간초과가 날 것이다!

Greedy and Stack

N개중 M을 지워서 최댓값을 구해야 한다는 조건은
N개중 N-M개를 '골라서' 최댓값을 구하는 것과 동일하다.

따라서 가장 차수가 큰 단위부터 큰 값을 Push하면서 선형 탐색을 진행한다.
선형 탐색 중 더 큰 값이 나오면 While문을 통해 Stack에서 Pop을 해주고 큰 값을 다시 Stack에 채워넣어주면 될 것 같다고 생각하고 바로 코드 구현에 나섰다.

이 때, Stack에 Push할 때 마다 picks (N-M, 즉 우리가 고를 수 있는 수의 갯수)를 빼주고, Stack에서 Pop 할 때에는 Picks를 더해줘서 가장 큰 값을 고를 수 있도록 해준다!

전체적인 코드는 아래와 같다.

import sys

input = sys.stdin.readline

n,m = map(int,input().split())
lst = []
tmp = input().rstrip()

for i in tmp:
    lst.append(int(i))

stack = []
picks = n-m
stack.append(lst[0])


picks-=1
for i in range(1,len(lst)): # 1,2,3,4,5,6
    if lst[i] <= stack[-1] and picks >= 1:
        stack.append(lst[i])
        picks-=1
    else:
        while ( len(stack) != 0 and stack[-1] < lst[i] and picks < n-i): # 더 뽑을 수 있는 갯수..?
            picks+=1
            stack.pop()
        if (picks >= 1 ):
            stack.append(lst[i])
            picks-=1

res = ""

for i in stack:
    res += str(i)

print(res)

전체 소요시간 : 40분

새벽에 잠이 오질 않아 누워서 생각해본 결과 바로 풀 수 있다고 판단하여 문제를 풀었는데 바로 풀렸다..!