스택 (Stack) 자료구조
큐와 유사한 자료구조 중 스택 자료구조가 있다.
스택은 큐와 다르게 LIFO (Last-in First-out) 의 방식으로 데이터를 관리한다. 즉, 마지막에 들어온 데이터가 먼저 아웃된다.
이러한 방식의 데이터 관리는 여러 방식에서 다양하게 쓰일 수 있는데, 우리가 흔히 컴퓨터 작업에서 사용하는 실행취소 및 복원 잡업 등에서 사용할 수 있다.
스택을 통해 구현할 수 있는 작업은 다음과 같다.
1) 맨 뒤에 새로운 데이터 추가 - append
2) 맨 뒤의 데이터 삭제 후 삭제된 데이터 리턴 - pop
3) 맨 뒤의 데이터에 접근 - stack[-1]
스택 또한 collections의 deque를 이용할 수 있다.
그러나, 큐의 경우와는 다르게 맨 뒤의 값에 접근하는 연산은 동적배열과 링크드 리스트 모두 O(1)의 시간이 걸리기 때문에, deque를 사용해 구현하던 리스트를 사용해 구현하던 stack을 이용하는데 시간 상 차이를 발생시키지 않는다.
그냥 편한 것을 사용하면 되겠다.
from collections import deque
stack = deque()
스택을 활용한 문제 중 가장 대표적인 문제는 괄호를 검사하는 문제이다
출처 : 백준 9012번 괄호
문제
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
출력
출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
예제 입력 1
6 (())()) (((()())() (()())((())) ((()()(()))(((())))() ()()()()(()()())() (()((())()(
예제 출력 1
NO NO YES NO YES NO
n = int(input())
brackets = []
for _ in range(n):
brackets.append(input())
def checker(bracket):
stack = [] # 빈 스택 생성
for i in range(len(bracket)):
if bracket[i] == '(': # 각 값이 '(' 일 땐, 스택에 append 해준다
stack.append(bracket[i])
else: # bracket[i] == ')' # 값이 ')' 일 땐
if len(stack) == 0: # 스택에 아무런 값도 없을 때 ')'이 입력되면 짝이 맞을 수 없다
return 'NO'
else: # 스택에 있던 '('와 ')'가 만나게 되므로 pop을 하여 짝이 맞는 괄호를 지워준다
stack.pop()
if len(stack) != 0: # for문을 다 나왔을 때 여전히 스택에 '('가 남아있다면 짝이 맞지 않으므로 No를 리턴
return 'NO'
else:
return 'YES' # for문에서 오류없이 나와 stack에 아무런 값도 없다면 모두 짝이 맞은 것이므로 YES 리턴
for bracket in brackets:
print(checker(bracket))
'(' 괄호가 나올 때마다 스택에 넣어주고, ')' 괄호가 나올 때마다 스택의 '('가 있는지 확인하고, 존재한다면 두 괄호를 짝을 맞춰 없애주고 그렇지 않다면 짝이 맞을 수 없으므로 NO를 리턴해준다.
해당 과정을 마친 후 stack의 값들을 확인하여 값들이 있을 경우는 '('에 맞는 충분한 ')'가 존재하지 않았던 것이므로 NO를, stack의 값이 존재하지 않는다면 모두 맞는 짝을 찾아 pop된 것이므로 YES를 리턴해준다.