백준 10828번 - 스택 [python]

Python 코드

import sys
def input():
    return sys.stdin.readline().rstrip()

n = int(input()) # 명령어의 수 개수
stack=[] # 스택

for i in range(n):
    cmd = input().split() # 명령어 입력받기
    if cmd[0] == 'push':
        stack.append(cmd[1])
    elif cmd[0] == 'pop':
        if len(stack) == 0:
            print(-1)
        else:
            print(stack.pop())
    elif cmd[0] == 'size':
        print(len(stack))
    elif cmd[0] == 'empty':
        if len(stack) == 0:
            print(1)
        else:
            print(0)
    elif cmd[0] == 'top':
        if len(stack) == 0:
            print(-1)
        else:
            print(stack[-1])

Python 코드 풀이

1. 코드에 대한 전체적인 풀이

해당 문제는 스택 자료구조를 구현하는 문제입니다.

스택 자료구조는 후입선출(LIFO, Last-In-First-Out) 방식을 따르는 자료구조로, 가장 최근에 추가된 요소가 가장 먼저 제거됩니다.

Python에서는 스택을 구현하기 위해 리스트를 사용할 수 있습니다. 'append' 메서드로 요소를 스택에 추가하고, 'pop' 메서드로 스택의 맨 위에 있는 요소를 제거할 수 있습니다.

본 문제에서는 먼저 명령어의 수를 입력받고, 이후 입력받은 명령어에 따라 스택에 요소를 추가하거나 제거합니다.

- 'push X' : X를 스택에 추가하는 연산입니다. 이때 'append' 메서드를 사용하여 스택에 추가합니다.
- 'pop' : 스택의 가장 위에 있는 정수를 제거하고 그 수를 출력합니다. 만약 스택이 비어 있다면 -1을 출력합니다. 이때 'pop' 메서드를 사용하여 스택의 맨 위에 있는 정수를 제거합니다.
- 'size' : 스택에 들어 있는 정수의 개수를 출력합니다. 이때 'len' 함수를 사용하여 스택에 들어 있는 요소의 개수를 출력합니다.
- 'empty' : 스택이 비어 있다면 1을, 그렇지 않다면 0을 출력합니다.
- 'top' : 스택의 가장 위에 있는 정수를 출력합니다. 만약 스택이 비어 있다면 -1을 출력합니다. 이때 'stack[-1]'을 이용하여 리스트의 맨 끝 요소를 출력합니다.

시간 복잡도를 계산해 보면, 처음에 input()으로 입력을 받을 경우 시간 제한 0.5초를 초과하는 경우가 있습니다. 그래서 입력을 'sys.stdin.readline()'을 사용하여 받았습니다. 이는 입력 속도를 빠르게 하는 방법입니다.

명령어의 수(N)에 따라 시간 복잡도가 결정됩니다. 즉, 각각의 명령어들의 연산은 O(1)의 시간 복잡도를 가지므로 전체 문제의 시간 복잡도는 O(N)입니다.