백준_9012 괄호

jiyseo·2024년 5월 11일

stack 괄호 백준 백준 9012 스택 코딩테스트 코테

코딩테스트

목록 보기

5/9

💡문제 분석 요약

https://www.acmicpc.net/problem/9012

괄호의 짝이 바르게 구성되어 있는지 확인하는 문제
올바른 괄호 문자열은 VPS(Valid PS)라고 함
n개의 괄호 문자열을 입력받아 문자열이 VPS인지 판단해 YES/NO로 출력

💡알고리즘 설계

💡 str = “(()((())()(” 일 때

stack

[ (, ( ] ← “(” 일 때 stack에 삽입

[ ( ] ← “)”일 때 queue의 마지막 요소 pop

[ (, (, (, ( ] ← 반복

[ (, ( ]

[ (, (, ( ]

[ (, ( ]

[ (, (, ( ] ← stack이 비어있지 않음 : VPS 아님

stack list를 만든다.
for loop를 통해 문자열을 하나씩 검사
- 문자가 “(”인 경우 stack에 append
- 문자가 “)”인 경우 stack의 마지막 요소 pop
  - stack의 길이가 0인 경우 (pop할 “(”가 없다) → NO → stack의 길이가 0이 되지 않도록 문자 추가하고 for문 break
stack의 길이가 0이 아닌 경우 → NO
n번 반복

💡코드

import sys

def bracket(bracstr) :
    answer = []
    for brac in bracstr :
        stack = []
        for b in brac :
            if b == "(" :
                stack.append(b)
            elif b == ")" :
                if len(stack) != 0 :
                    stack.pop(-1)
                else :
                    stack.append("(")
                    break
        if len(stack) == 0 :
            answer.append("YES")
        else : answer.append("NO")
    for a in answer :
        print(a)

n = int(sys.stdin.readline())
bracstr = []
for i in range(n) :
    bracstr.append(sys.stdin.readline())
bracket(bracstr)