BOJ 2812번: 크게 만들기

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

2812번: 크게 만들기

스택에 주어진 수의 앞에서부터 하나씩 넣으면서 기존에 있던 스택 top의 수가 새로 넣을 수보다 작은 경우에 더 크거나 같은 수가 나올때까지 그리고 스택이 비지 않을때까지 pop한다.

그렇게 했음에도 K번 pop되지 않은 경우에는 마지막에 출력할때 앞에서부터 N-K만큼의 길이만 출력하면 된다.

 

스택으로 구현하였는데, 기존에 푼 방법이 속도가 더 빨랐다. 이건 pop이 아니라 del을 사용했으며 마지막에 출력할 때 반복문을 사용하지 않고 join을 사용해서 그런 것 같다. 같이 첨부하겠다.

1. 스택 - 처음에 푼 방법

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
num = list(map(int, input().rstrip()))
st = []

k = 0
for i in range(N):
    if (k!=K):
        if (len(st)==0):
            st.append(num[i])
            
        elif (st[-1] > num[i]):
            st.append(num[i])
            
        else:
            while(st and st[-1] < num[i]):
                st.pop()
                k += 1
                if (k==K):
                    break
            st.append(num[i])
    else:
        st.append(num[i])
        
for i in range(N-K):
    print(st[i], end='')

2. 기존에 풀었던 방법 - 아마 구글링해서 풀었을 듯..?

import sys
n,k=map(int, sys.stdin.readline().split())
s=sys.stdin.readline().rstrip()
s=list(s)

ans=[]
ans.append(s[0])
length=n-k

for i in range(1,len(s)):
    while k>0 and ans and ans[-1]<s[i]:
        del ans[-1]
        k-=1
    ans.append(s[i])
        
print(''.join(ans[:length]))

3. 합쳐본 방법... 2번보다는 느리지만 1번 보다는 빠르다.

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
num = list(map(int, input().rstrip()))
st = []
st.append(num[0])

for i in range(1, N):
    while K>0 and st and st[-1]<num[i]:
        st.pop()
        k-=1
    st.append(num[i])
        
for i in range(N-K):
    print(st[i], end='')