[자료구조] [BJ10828] 스택

코드 플러스

🚩 문제 설명

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

10828번: 스택

BJ10828

⏱️ 시간 복잡도
: O(N)으로 해결 가능하다.

◾ 스택을 구현하고 주어진 명령어에 따라 숫자를 반환하는 문제

◾ 명령어 설명

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

◾ 문제의 이해는 다음과 같다.

 

✔️ 예시

stack	return
	push 1
	push 2
	top ➡️ 2
	size ➡️ 2
	empty ➡️ 0
	pop ➡️ 2
	pop ➡️ 1
	pop ➡️ -1
	size ➡️ -1
	empty ➡️ 1
	pop ➡️ -1
	push 3
	empty ➡️ 0
	top ➡️ 3

 

 

 

 

---

 

 

 

✅ 입출력

✔️ 예제 1

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

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

 

✔️ 예제 2

7
pop
top
push 123
top
pop
top
pop

-1
-1
123
123
-1
-1

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

n = int(input())
com = [input() for _ in range(n)]  # 주어진 명령어
stack = []  # 스택 배열


def empty(stack):
    if len(stack) == 0:
        return True
    return False


for c in com:
    splited = c.split()

    if splited[0] == 'push':
        stack.append(splited[1])
    if splited[0] == 'top':
        if empty(stack):
            print(-1)
        else:
            print(stack[-1])
    if splited[0] == 'size':
        print(len(stack))
    if splited[0] == 'pop':
        if empty(stack):
            print(-1)
        else:
            print(stack[-1])
            stack.pop()
    if splited[0] == 'empty':
        if empty(stack):
            print(1)
        else:
            print(0)

💬 Point

➡️  com = [input() for _ in range(n)] 으로 명령어 배열 입력 받기
➡️  empty 함수로 스택이 비었는지 아닌지 확인한다.

◾ 해당 명령어 마다 조건을 만들어준다.

◾ stack 배열이 비었는지 아닌지는 empty(stack) 함수를 이용하여 확인한다.

◾ N의 최대값이 10만 이므로 O(N)이면 10^5 / 10^8 하면 = 1/10^3 = 0.001초 정도 된다. 100ms 정도. 

 

 

 

 

 

 

 

 

 

 

 

 

 

---