[백준/Baekjoon] 10828번: 스택

1. 문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

2. 입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

3. 출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

4. 예제 입력 1

14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top

5. 예제 출력 1

2
2
0
2
1
-1
0
1
-1
0
3

6. 예제 입력 2

7
pop
top
push 123
top
pop
top
pop

7. 예제 출력 2

-1
-1
123
123
-1
-1

8. 풀이

스택(Stack) 은 자료구조 중 하나로, 후입선출(LIFO: Last In First Out) 특성을 가지고 있다. 이를 연결 리스트를 이용하여 구현하면 다음과 같다.

# 연결 리스트를 담을 Node 클래스 정의
class Node:
    def __init__(self, item, next):
        self.item = item  # 노드의 값
        self.next = next  # 다음 노드를 가리키는 포인터


class Stack:
    def __init__(self):
        self.last = None

    # 요소를 컬렉션에 추가하는 push() 연산
    def push(self, item):
        self.last = Node(item, self.last)

    # 가장 최근에 삽입된 요소를 제거하는 pop() 연산
    def pop(self):
        item = self.last.item
        self.last = self.last.next
        return item

구현 원리를 그림으로 나타내면 다음과 같다.

출처 - Java2Blog

아래 코드는 연결 리스트가 아닌 Python 자체 함수와 리스트를 이용하여 스택을 구현한 것이다.

리스트의 값을 제거할 때는 remove(), pop(), del 함수가 사용된다. remove() 함수는 제거하려는 값의 인덱스가 아니라 값 자체를 입력하는 것이고, pop() 함수는 문제에서 구현해야 하는 것이기 때문에 배제했다.

또한 입력에서 시간 초과 방지를 위해 sys 모듈의 sys.stdin을 사용한다. 이유는 이 글 에서 확인할 수 있다.

9. 코드

from sys import stdin


class Stack:
    def __init__(self):
        self.len = 0
        self.list = []

    def push(self, num):
        self.list.append(num)
        self.len += 1

    def pop(self):
        if self.size() == 0:
            return -1
        item = self.list[self.len - 1]
        del self.list[self.len - 1]
        self.len -= 1
        return item

    def size(self):
        return self.len

    def empty(self):
        if self.size() == 0:
            return 1
        else:
            return 0

    def top(self):
        if self.size() == 0:
            return -1
        return self.list[-1]


n = int(stdin.readline().strip())
stack = Stack()

for _ in range(n):
    data = stdin.readline().strip().split()
    command = data[0]

    if command == "push":
        stack.push(data[1])
    elif command == "pop":
        print(stack.pop())
    elif command == "size":
        print(stack.size())
    elif command == "empty":
        print(stack.empty())
    elif command == "top":
        print(stack.top())