4/17 스택(Stack)

스택(Stack)이란

: 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있도록 제한된 선형으로 나열된 자료구조이다. 쉽게 비유하자면 비어있는 '프링글스 통'을 생각해보자. 과자를 먹을 때, 맨 위에 있는 과자부터 먹을 수 있고, 새로 과자를 추가한다면 먼저 들어간 과자보다 위에 쌓이는 형태일 것이다.

스택은 가장 먼저 들어간 자료가 맨 아래쪽에 쌓이고, 가장 나중에 들어간 자료가 맨 위에 쌓이기 때문에, 먼저 들어간 자료일 수록 나중에 나오고, 늦게 들어갈 수록 더 빨리 나온다.
이를 후입선출 구조라고 하고, 영어로는 LIFO : Last In First Out 라고 한다.

Stack 기본연산

push()
스택에 원소를 추가한다.
pop()
스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.
peek()
스택 가장 위에 있는 원소를 반환한다. (삭제하지는 않는다.)
empty()
스택이 비어있다면 1, 아니면 0을 반환한다.
.

사용법(내장함수 이용)

a_list.append(1) : 괄호 안의 요소를 리스트 맨 뒤에 넣음

a_list = [1,2,3]
a_list.append(1)
=> [1,2,3,1]
a_list.pop() : 리스트의 맨 뒤에 요소를 꺼내고 리스트에서 삭제함

a_list = [1,2,3]
a_list.pop()
=> [1,2]

print(a_list.pop())
출력: 2
a_list : [1]

3. 클래스를 이용한 스택 구현

Stack Class

class stack:
    def __init__(self):  # 스택 객체 생성
        self.items = []

    def push(self, item):  # 스택 요소 추가 push(.append())
        self.items.append(item)

    def pop(self):  # 스택 맨 뒤 요소 삭제하고 리턴 pop()
        return self.items.pop()

    def peek(self):  # 스택 맨 뒤 요소 리턴
        return self.items[-1]

    def isEmpty(self):  # 스택이 비었는지 확인(비었으면 True 리턴)
        return not self.items


stk = stack()  # stack 객체 생성
print(stk)  # stack object 생성 확인

print(stk.isEmpty())  # 처음에는 아무것도 들어있지 않으므로 True 출력
stk.push(7)  # stk 에 7 넣음 : [7]
stk.push(8)  # stk 에 8 넣음 : [7,8]
stk.push(9)  # stk 에 9 넣음 : [7,8,9]
print(stk.items) #= > [7, 8, 9]

print(stk.pop())  # stk 맨 마지막 값을 꺼내온다. 9를 꺼냈으니 출력 : 9
print(stk.items)  # [7, 8] 꺼내지고 남은 값들

print(stk.peek())  # stk 맨 마지막 값을 꺼내지 않고 출력만한다 출력 : 8
print(stk.items)  # [7, 8] 아무 값도 사라지지 않은걸 알 수 있다

print(stk.pop())  # stk 마지막 값 8 꺼내지면서 출력 : 8
print(stk.pop())  # stk 마지막 값 7 꺼내지면서 출력 : 7

print(stk.isEmpty())  # 객체에 아무것도 들어있지 않으므로 True 출력
print(stk.items)  # 비어 있으므로 [] 출력

스택을 활용한 문제
문제 링크

괄호

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 162654 75365 54266 45.279%

문제
괄호 문자열(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

예제 입력 2
3
((
))
())(()

예제 출력 2
NO
NO
NO

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
    stack = []
    bracket = input().rstrip()
    for i in bracket:
        if i == "(":
            stack.append(i)
        elif i == ")":
            if len(stack) == 0:
                stack.pop
                stack.append(i)
                break
            else:
                stack.pop()
        
    if len(stack) == 0:
        print("YES")
    else:
        print("NO")