[알고리즘] 스택(Stack) 정리 & 문제 풀이(Python)
스택
: 자료구조 중 하나로, 먼한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 구조이다.
- 파이썬은 스택 자료구조를 제공하지 않는다. 기본 클래스인 list를 통해 스택을 흉내낼 수 있다.
스택의 연산
- push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
- pop(): 스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.
- peek(): 스택 가장 위에 있는 원소를 반환한다. (삭제하지는 않는다.)
- isEmpty(): 스택이 비어있다면 1, 아니면 0을 반환한다.
대표적인 문제 및 사용
- 웹 브라우저 방문기록(뒤로가기)
- 실행 취소(undo)
- 역순 문자열 만들기
- 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호검사)
- 후위 표기법 계산
Stack 구현
파이썬에서는 스택을 리스트 또는 연결리스트로 구현한다.
강력한 내장함수를 제공해주는 리스트로 구현하면 정말 간단하다.
S.append() 리스트 맨 끝에 원소를 추가한다. 시간복잡도는 O(1)이다.
S.pop(i) 리스트의 i번째 원소를 삭제한다. S.pop(-1)은 맨 앞에 있는 원소를 삭제한다. 시간복잡도는 마찬가지로 O(1)이다.
다음은 가장 기본의 연산을 가지는 스택이다.
class Stack:
# 리스트를 이용한 스택 구현
def __init__(self):
self.top = []
# 스택 크기 반환
def __len__(self) -> bool:
return len(self.top)
# 스택에 원소 삽입
def push(self, item):
self.top.append(item)
# 스택 가장 위에 있는 원소를 삭제하고 반환
# 리스트 인덱스는 0부터 시작, 뒤에서부터 위치를 지정하는 경우는 -1부터 시작!
def pop(self, item):
if not self.isEmpty():
return self.top.pop(-1)
else:
print("Stack underlow")
exit()
# 스택 가장 위에 있는 원소를 반환
def peek(self, item):
if not self.isEmpty():
return self.top[-1]
else:
print("underflow")
exit()
# 스택이 비어있는지를 bool값으로 반환
def isEmpty(self) -> bool:
return len(self.top) == 0[백준] 10828번 스택
문제링크 https://www.acmicpc.net/problem/10828
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
push X: 정수 X를 스택에 넣는 연산이다.
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 스택에 들어있는 정수의 개수를 출력한다.
empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
# sys 모듈은 파이썬 인터프리터가 제공하는 변수와 함수를 직접 제어할 수 있게 해주는 모듈
# 시간 초과를 해결하기 위한 sys 선언
import sys
# 첫째 줄에 명령의 수 N이 주어짐
N = int(sys.stdin.readline())
# 파이썬은 스택 자료구조를 제공하지 않는다. python은 list로 stack을 흉내 낼 수 있음.
stack = []
# 0부터 N-1까지 반복
for _ in range(N):
# 임의의 개수의 정수를 한 줄에 입력받아 리스트에 저장할 때
command = list(sys.stdin.readline().split())
# split(): 문자열을 나눠주는 함수
# list(): 자료형을 리스트형으로 변환해주는 함수
if command[0] == 'push':
stack.append(command[1])
elif command[0] == 'pop':
if len(stack) == 0:
print(-1)
else:
print(stack.pop())
elif command[0] == 'size':
print(len(stack))
elif command[0] == 'empty':
if len(stack) == 0:
print(1)
else:
print(0)
elif command[0] == 'top':
if len(stack) == 0:
print(-1)
else:
print(stack[-1])문제를 풀 때 시간초과가 계속 났다. 문제점은 input 때문이었는데 input 대신에 값을 입력받는데 더 빠른 readline을 사용해줬다.
input()의 경우 사용자의 입력을 받아서 -> 문자열로 변환 -> strip(양끝 공백 제거처리) 과정을 거친다. 반면, sys.stdin.readline()의 경우 개행 문자도 입력을 받을 수 있다고 한다. 단, 이때는 맨 끝의 개행문자까지 같이 입력받으므로 문자열을 저장하고 싶다면 rstrip(오른쪽 공백제거)을 사용한다.
import sys
N = int(sys.stdin.readline())
혹은
import sysinput = sys.stdin.readline()
N = int(input())
Python에서 Stack 이용하기
- stack은 list로 선언 (stack =[])
- push = stack.append()
- pop = stack.pop()
- isEmpty = 0 if stack else 1
- size = len(stack)
- top = stack[-1]
import sys
input = sys.stdin.readline()
n = int(input())
stack = []
class Stack:
def push(x):
stack.append(x)
def pop():
if not stack:
return -1
return stack.pop()
def size():
return len(stack)
def empty():
if not stack:
return 1
return 0
def top():
if not stack:
return -1
return stack[-1]
for _ in range(n):
command = sys.stdin.readline().split()
if 'push' in command:
push(command[1])
elif 'top' in command:
print(top())
elif 'size' in command:
print(size())
elif 'empty' in command:
print(empty())
else:
print(pop())
# 이 코드는 왜 컴파일에러가 나는가!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!![도움을 주신 블로그들 :) ]
https://velog.io/@yeseolee/Python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack