https://www.acmicpc.net/problem/2812
2812번: 크게 만들기
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
스택에 주어진 수의 앞에서부터 하나씩 넣으면서 기존에 있던 스택 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='')
'알고리즘💻 > 스택&큐&덱' 카테고리의 다른 글
BOJ 20301번: 반전 요세푸스 (0) | 2021.07.25 |
---|---|
BOJ 10799번: 쇠막대기 (0) | 2021.07.24 |
BOJ 9012번: 괄호 (0) | 2021.07.24 |
BOJ 20923번: 숫자 할리갈리 게임 (0) | 2021.07.23 |
BOJ 18115번: 카드 놓기 (0) | 2021.07.22 |