[스택]Stack 정리_1(with. 백준,9012, 괄호)

1. 정의

 1) 뜻 : 스택(stack)은 데이터를 임시 저장하는 기본 자료구조

 2) 입출력 순서 : 후입 선출

  - 쉽게말해 데이터를 넣을때(push) 마지막 데이터에 들어가며, 빼면(pop) 마지막 데이터가 나온다.

 

2. 기본 용어

 1) Push 

  - 스택에서 데이터를 넣을때 사용하는 용어

  - 마지막에 데이터가 추가되는 것을 볼 수 있다.

 2)Pop 

  - 스택에서 데이터를 가져올때 사용하는 용어

  - 마지막의 데이터를 가져오게 된다. 

 3) Stk

  -  push한 데이터를 저장하는 스택본체의 list형 배열 이다.

 4) Stk의 bottom, top

  - 말그대로 Stk의 가장 밑이 bottom, 스택에 들어있는 데이터의 가장 마지막 데이터를 top이라고 한다. 

  - 주의해야 할 것은 데이터가 가장 처음 쌓이는 곳은 stk[0]이다.

 5) Capacity(스택의 크기)

  - 스택에 쌓을 수 있는 크기를 말한다.

 6) *Ptr(스택포인터)

  - 현재 스택에 쌓여 있는 데이터의 개수를 나타내는 정수값이다.

  - 스택이 push되면 이 prt에 쌓이게 된다. 

 

3. 예시 문제(백준,9012, 괄호)

 1) 문제

문제

 2) 문제 해석

  - 직관적으론 문제에서 말하는 올바른 괄호(VPS)가 맞는지 틀린지 찾는 문제이다. 

  - 스택을 연관하여 발견해야 할 부분은 주어진 문자(괄호)를 하나씩 받아 만든 스택에 넣을지, 말지, 기존껄 pop할지 판단해야 한다.

 3) 코드 방향성

  - 케이스를 받는다.

  - 케이스의 숫자만큼 받은 괄호가 담긴 문자열을 반복문을 통해 괄호 하나씩 확인한다.

  - stack이란 리스트에 push, pop을 반복하며 리스트가 비어있다면(len(stack)==0) 'YES'를 찍어주고, 그렇지 않다면 'NO'를 찍어 줄꺼다.

  - 이부분까지만 이해 하면서 코드를 보자

 4) 코드

import sys
# 09. https://www.acmicpc.net/problem/9012 : 괄호
input = sys.stdin.readline

for _ in range(int(input())): # 첫 줄의 케이스를 받고 그 range만큼 괄호를 받는다.
    s = input() # 괄호를 받는다
    stack = [] # 스택으로 쌓을 빈 리스트 
    for c in s: # 괄호 문자열에서 하나씩 확인
        if c == '(': # 열린 괄호면 스택에 추가
            stack.append(c) # 나중에 ')'가 들어올때 빼낼 꺼다.
        elif c == ')': # 닫힌 괄호이면서 
            if len(stack)==0 or stack[-1] != '(':# 리스트가 없거나 스택의 마지막이 ')'이면 
                stack.append(')') # 스택에 추가 하고 
                break # 반복문 나가

            stack.pop() # 스택에 ( 열린괄호가 있으면 pop

    # 스택에 리스트가 짝으로 있다면 YES출력, 없거나 하나면 NO출력
    if len(stack) == 0:
        print('YES')
    else:
        print('NO')

  - 다른 블로그를 참조하였으며, 나에게 많이 어려운 코드다.

  - 하지만 스택의 정의를 잘 살린것 같고 생각의 전환이 많이 들어같다는 개인적인 생각으로 도전해 봤다.