[백준] 10828번 해설 - Python

문제

https://boj.kr/10828

10828번: 스택

 

해설

스택에 대한 기본적인 문제이다. 스택은 pop과 push 연산을 기본적으로 가지고, push는 새로운 아이템을 추가하는 연산, pop은 가장 최근에 추가된 아이템을 꺼내는 연산이다. 그럼 간단하게 소스코드를 작성할 수 있겠다.

n = int(input())
stack = list()

for _ in range(n):
    prompt = input().split()
    command = prompt[0]
    if command == "push":
        stack.append(int(prompt[1]))
    elif command == "pop":
        if len(stack) == 0:
            print(-1)
        else:
            print(stack.pop())
    elif command == "size":
        print(len(stack))
    elif command == "empty":
        if len(stack) == 0:
            print(1)
        else:
            print(0)
    elif command == "top":
        if len(stack) == 0:
            print(-1)
        else:
            print(stack[-1])
    else:
        print("Wrong Command")

근데 틀렸다.. 이유를 보니 시간 초과라고 한다. 즉, 어디선가 많은 연산이 사용되고 있다는 것이다. 내가 바꾼 부분은 2곳이다. 

 

 

• input()은 너무나 간단한 튜닝방법이다. import sys로 sys.stdin을 가져와 Input()을 대체할 수 있다.
• append()와 pop()연산은 생각보다 많은 연산량을 요구한단다. 그럼 일단은 append()를 사용 안하게 stack 리스트의 인덱스를 최대로 늘리고, pop은 마지막 인덱스 위치를 기억하고 뒤에 값들은 무시하는 식으로 작성하면 될 것 같다.

 

 

튜닝한 코드는 이렇게 생겼다.

import sys

n = int(input())
stack = [0 for _ in range(100000)]
last_index = -1

for each in sys.stdin:
    prompt = each.split()
    command = prompt[0]
    if command == "push":
        last_index += 1
        stack[last_index] = int(prompt[1])
    elif command == "pop":
        if last_index == -1:
            print(-1)
        else:
            print(stack[last_index])
            last_index -= 1
    elif command == "size":
        print(last_index + 1)
    elif command == "empty":
        if last_index == -1:
            print(1)
        else:
            print(0)
    elif command == "top":
        if last_index == -1:
            print(-1)
        else:
            print(stack[last_index])
    else:
        print("Wrong Command")

 

성공!