Stack 스택

woohobi·2021년 10월 5일
0

알고리즘

목록 보기
4/5

스택은 기본 자료구조 중 하나로 First in, Last out 방식으로 동작합니다. 즉, 가장 먼저 들어간 원소가 가장 마지막에 나오게 됩니다.

위의 이미지와 같은 방식으로 동작하는데, 맨 처음 빈 list에서 push 3, push 7, push 6을 하면 3 위에 7, 6이 삽입되는 것을 볼 수 있고, pop 연산을 하면 가장 위에 있는 6이 삭제되는 것을 볼 수 있습니다.
이렇듯 stack은 삽입과 삭제 연산이 list의 top에서 이루어지는 것을 볼 수 있고 stack 문제에서는 top 부분을 주의 깊게 봐야합니다.

python에서 list가 stack 자료구조로 동작하기 때문에, 쉽게 구현할 수 있습니다.

# python 에서 list 선언 방법
stack =[]
stack= list()

#append와 pop은 가장 위에 있는 요소인 top에 대해서만 처리를 해주면 되서 시간 복잡도는 O(1) 입니다.
stack.append(1)
stack.append(6)
stack.append(2)
#tuple 형태도 삽입할 수 있습니다.
stack.append((1,2))

#가장 위에 있는 (1,2)가 리턴됩니다.
top = stack.pop()

#1,6,2 가 출력됩니다.
print(stack)

#list의 -1번째 index는 top인 2입니다.
print(stack[-1])

#리스트가 비어있는지 체크
if len(stack)==0: 이렇게 체크해줄수도 있지만,

if stack: 이라고 써주면 stack이 비어있지 않을 때 True를 리턴해서 훨씬 python스러운 코드를 쓸 수 있습니다.

반대로, 아래코드는 비어있을때만 True 를 리턴합니다.
if not stack: 

예시 문제

괄호와 관련된 괄호 문제는 스택에서 기본 유형이라고 할 만큼 자주 나오고 여러가지 유형으로 변형되어 출제됩니다.

#문제에서 봐야할 것은 괄호가 올바르게 형성 되었는지를 확인해주어야 한다.
import sys
input = sys.stdin.readline

n= int(input())

for i in range(n):
    isBracket= True
    bracket = list(map(str, input().strip()))
    arr = list()
    for x in bracket:
    	#여는 괄호면 stack에 삽입
        if x == "(":
            arr.append("(")
        # 닫는 괄호면 여는 괄호가 stack에 있는지 확인, 없다면 올바르지 않은 괄호
        elif x== ")":
            if not arr:
                isBracket = False
                break
            arr.pop()
    #중간에 break로 올바르지 않은 괄호
    if not isBracket:
        print("NO")
    else:
    	#arr가 비어있지 않으면, 여는 괄호가 더 많은 상태-> 올바르지 않은 괄호
        if arr:
            print("NO")
        else:
            print("YES")

stack의 기본 유형인 괄호를 살펴봤는데, 사실 이 문제는 stack을 이용하지 않고 괄호 개수만 카운팅해도 풀 수 있습니다. 하지만 stack에 넣어서 top을 보며 확인하는 아이디어는 여러 문제에 변형되어 출제되어서 꼭 챙겨갈 아이디어입니다.

profile
CDD - Coffee Driven Development

0개의 댓글