백준(BAEKJOON) 9012 괄호 - 파이썬

 

< 풀이 방법 >

Stack 활용

* Stack은 LIFO(Last In First Out)의 형태를 갖는 자료구조

- Push, Pop 등의 메서드 이용

 

< 접근 방법 >

1. 입력받은 문자열을 앞에서부터 순차적으로 하나씩 접근

    * 문자열은 크게   여는 괄호 "(",  닫는 괄호 ")" ,  기타(문자) 로 이루어져 있음

 

2.

(1) stack을 만들어두고 "("가 나오면 하나씩 push

    - 파이썬에서는 리스트의 append, pop을 활용하면 됨

(2) last_check = 0 이라는 변수를 만들어 둠 --> 마지막에 닫는 괄호 ")" 가 오는 경우 대비

 

3. ")" 가 나왔을 때 스택에서 하나씩 pop함 --> 담아뒀던 여는 괄호 "("가 하나씩 빠짐

  - 예외 상황

    - stack이 비어있는 경우

        - 입력받은 문자열을 순회하는 for문을 break해서 끝냄

    - 마지막에 닫는 괄호 ")" 가 오는 경우

        - 2-(2)에서 만들어 둔 last_check를 변경

 

4. 문자열을 순회하는 for문이 종료된 후

stack이 비어있지 않거나 /  last_check가 처음 만든 0과 동일하지 않으면 "NO"를 출력함

그 외의 경우 "YES" 출력

 

 

< 코드 >

iter_num = int(input())

for each_iter in range(iter_num):
    paranthesis = input()
    stack_list = []
    last_check = 0    # 마지막에 ")"가 오는 경우 대비

    for str_idx in range(len(paranthesis)):
        each_str = paranthesis[str_idx]

        if each_str == "(":
            stack_list.append(each_str)
        elif each_str == ")":
            if not stack_list:    # 리스트 비어있을 경우
                last_check += 1
                break
            else:
                stack_list.pop()
        else:
            continue
    if (len(stack_list) != 0) or last_check != 0:
        print("NO")
    else:
        print("YES")

 

21.12.27일 다시 풀어본 코드

import sys
# vps: Valid Paranthesis String
num = int(sys.stdin.readline())

for _ in range(num):
    target = list(sys.stdin.readline().strip())
    temp = [] # 입력 괄호 문자열 확인용 빈 스택
    # "(" 이면 스택에 추가
    # 스택이 비어있지 않을 때 ")" 이면 스택 pop, 스택이 비어있을 때면 break, not vps
    for x in target:
        if x == "(":
            temp.append(x)
        else:
            if len(temp) == 0:
                temp.append(x)
                break
            else: temp.pop()

    if len(temp) == 0:
        print("YES")
    else: print("NO")