[스택] 백준 2812번 크게 만들기 with Python3

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

2812번: 크게 만들기

 

문제

내 풀이 -실패

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
str = list(input().rstrip())
stack = list()


print(str)

for i in range(n-1, 0, -1):
    if len(stack) == n-m:
        if int(str[i]) > int(stack[0]):
            stack.popleft()
            stack.appendleft(str[i])
        elif int(str[i]) == int(stack[0]):
            stack.pop()
            stack.appendleft(str[i])
        else:
            continue
    else:
        stack.appendleft(str[i])
print(str(list(stack)))

해설

제일 큰 수를 만들어야하기에, 뒤에서부터 시작해서 검증을 했다.

무조건 제일 큰 자리만 바꾸면 해결이 될거라고 생각했는데 그렇지가 않았다.

이 문제는 말그대로 숫자가 작은 순서대로 지우고 나야 제일 큰 수가 나오는 것이었다.

 

 

정답 풀이

import sys

n, k = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().strip()))

result = []
delNum = k

for i in range(n):
    while delNum > 0 and result:
        if result[len(result) - 1] < nums[i]:
            result.pop()
            delNum -= 1
        else:
            break
    result.append(nums[i])
    # print(f'i는{i}')
    # print(result)


for i in range(n-k):
    print(result[i], end="")

출처:https://kyoung-jnn.tistory.com/entry/%EB%B0%B1%EC%A4%802812%EB%B2%88%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%ED%81%AC%EA%B2%8C-%EB%A7%8C%EB%93%A4%EA%B8%B0-%EA%B7%B8%EB%A6%AC%EB%94%94-Greedy

 

해석

그런데 해답을 보니 너무 생각보다 코드가 쉬워보여서 당황스러웠다.

단순히 result의 제일 뒤 수와 비교를 하면서 delNum이라는 개념을 섞으면 답을 만들 수 있다니.

 

조금 허망하면서 대단하기도 하다. 

 

이 문제의 경우 deque를 사용하면 오히려 시간이 증가한다..? 왜지?

 

라이브러리가 들어와서 그것을 활용하는 과정에서 시간이 더욱 소모되는 것인가?

일반적으론 stack을 리스트로 사용하는 과정에서 deque 형식으로 변경하면, pop, append의 시간복잡도가 O(1)로 떨어지는걸로 아는데

 

아래는 예제 3의 과정이다

10 4       
4177252841

i는0
deque([4])
i는1
deque([4, 1])
i는2
deque([7])  #이곳에서 위 코드의 강점이 나온다. 필요할 경우 모든 element를 바꿔버린다.

                #이를 통해 가장 큰 자리 수에 가장 큰 수가 올 수 있게 해준다
i는3
deque([7, 7])
i는4
deque([7, 7, 2])
i는5
deque([7, 7, 5])
i는6
deque([7, 7, 5, 2])
i는7
deque([7, 7, 5, 8])
i는8
deque([7, 7, 5, 8, 4])
i는9
deque([7, 7, 5, 8, 4, 1])

775841