백준 문제 중 10828번, 스택, ‘스택’
백준 문제 중 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보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
풀이
from typing import Any
import sys
class Stack:
def __init__(self,n:int)->None:
self.stk=[None]*n
self.ptr=0
self.no=0
def is_empty(self)->bool:
return self.no<=0
def push(self,x:int)->None:
self.stk[self.ptr]=x
self.ptr+=1
self.no+=1
def pop(self)->Any:
if self.is_empty():
print(-1)
return -1
self.ptr-=1
self.no-=1
print(self.stk[self.ptr])
def size(self)->int:
print(self.no)
def empty(self)->int:
if self.is_empty():
print(1)
else:
print(0)
def top(self)->Any:
if self.is_empty():
print(-1)
else:
print(self.stk[self.ptr-1])
n = int(sys.stdin.readline())
x = Stack(n)
cmds = [None]*n
for i in range(n):
cmds[i] = sys.stdin.readline().split()
for cmd in cmds:
if cmd[0]=='push':
x.push(int(cmd[1]))
elif cmd[0]=='pop':
x.pop()
elif cmd[0]=='size':
x.size()
elif cmd[0]=='empty':
x.empty()
elif cmd[0]=='top':
x.top()
2
2
0
2
1
-1
0
1
-1
0
3
배운점
스택을 파이썬으로 구현하는법을 배웠다.
보충
연결리스트로 파이썬 구현 연결리스트의 코드는 다음 링크에서 가져왔다. LinkedList-(1)-SingleLinkedList
from typing import Any,Type
# 노드 클래스 선언
class Node:
def __init__(self,data:Any,next=None):
self.data = data
self.next = next
# 싱글 링크드리스트 클래스 선언
class SingleLinkedList:
# 시작 head, 현재 cur, 갯수 no 선언
def __init__(self):
self.head = None
self.cur = None
self.no = 0
# dunder 함수로 len구현
def __len__(self):
return self.no
# 원하는 데이터를 찾는 함수
def search(self,data:Any)->int:
# data의 인덱스를 나타낼 변수
cnt = 0
# head 부터 시작해서 노드가 none이 될때까지 next
p = self.head
while p is not None:
# 스캔중 data 발견시 return cnt
if p.data == data:
self.cur = p
return cnt
p = p.next
cnt+=1
# 검색 실패시 return -1
return -1
# 머리에 노드추가 함수
def add_first(self,data:Any)->None:
# 기존의 self.head를 next로 data를 data로 갖는 노드 추가
# cur, no 업데이트
self.head = self.cur = Node(data,self.head)
self.no+=1
# 꼬리 노드추가 함수
def add_last(self,data:Any)->None:
# 리스트가 비었다면 머리추가와 동일
if self.head is None:
self.add_first(data)
else:
# p.next가 None 즉 마지막 노드까지 스캔
p = self.head
while p.next is not None:
p = p.next
# 마지막노드 p의 next에 data를 data로 갖는 노드 추가
# cur, no 업데이트
p.next = self.cur = Node(data)
self.no+=1
# 머리노드 삭제 함수
def remove_first(self)->bool:
# 리스트가 비었다면 삭제 실패 False 반환
if self.head is None:
return False
# head가 None이 아니라면 head를 삭제
# cur, no 업데이트 후 True 반환
else:
self.head = self.cur = self.head.next
self.no-=1
return True
# 꼬리노드 삭제 함수
def remove_last(self)->bool:
# 리스트가 비었다면 false 반환
if self.head is None:
return False
# p.next가 none 즉 마지막 노드까지 스캔
# 단. pre에 이전 p를 저장하며 진행
else:
p = self.head
pre = self.head
while p.next is not None:
pre = p
p = p.next
# 마지막 노드 p의 전 노드 pre의 next를 None으로 업데이트
pre.next = None
self.cur = pre
self.no-=1
return True
# 노드x를 삭제하는 함수
def remove(self,x:Node)->None:
# 리스트가 비었다면 false 반환
if self.head is None:
return False
else:
p = self.head
# p의 next와 x가 일치할때 까지 진행
while p.next is not x:
p = p.next
# 마지막 노드까지 없다면 false 반환
if p is None:
return False
# p의 next가 x이므로 p.next에 x의 next 대입
p.next = x.next
self.cur = p
self.no-=1
def remove_cur_node(self)->None:
self.remove(self.cur)
def print_cur_node(self)->None:
if self.cur is None: print('-1')
else: print(self.cur.data)
def print(self)->None:
p=self.head
while p is not None:
print(p.data)
p=p.next
def clear(self)->None:
while self.head is not None:
self.remove_first()
self.cur = None
self.no
class Stack(SingleLinkedList):
def push(self,data):
self.add_last(data)
def pop(self):
self.print_cur_node()
self.remove_cur_node()
def size(self):
print(self.no)
def empty(self):
print(1 if self.no<=0 else 0)
def top(self):
self.print_cur_node()
x=Stack()
x.push(1)
x.push(2)
x.push(4)
x.push(9)
x.pop()
x.pop()
x.size()
x.empty()
x.top()
9
4
2
0
2
Leave a comment