[백준] 9012번 괄호

백준 9012

 

스택 공부하면서 풀이했는데

익숙하다 했더니 아카데미에서 배웠던 문제이다 (ㅋㅋ)

 

Stack 자료구조를 이용하면 풀이할 수 있다.

Stack 자료구조는 Last in First Out(LIFO) 구조를 말하고 Stack을 하나 만들어서 stack = [] 형태로 두고 풀이하면 된다

 

***

처음에 고안했던 방법은 (틀렸지만)

list로 input을 받아서 list의 원소들을 보면서 list[0]과 list[-1]이 다르면 쌍으로 묶어서 pop 하고,

같은 경우 하나만 pop 해서 다른 리스트에 넣으면 어떻게 되지 않을까... 라는 생각을 했지만? indexing에서 부터 out of range 오류가 나서 Stack으로 풀이하였다... 

***

 

Pseduo-code

 

먼저 pseudo-code를 작성해보면, 

1. input을 list 형태로 받는다.

2. stack 이라는 빈 리스트를 생성한다.

3. input으로 받은 리스트를 순환하면서 만약 '(' 이 존재한다면 stack에 집어넣는다.

4. input으로 받은 리스트를 순환하는데 만약 ')'이 존재하고 stack에 '(' 이 있다면 stack을 비운다.

5. input으로 받은 리스트를 순환하는데 만약 ')'이 존재하고 stack 에 '('이 없다면 stack에 ')'를 집어넣는다.

 

이렇게 되면 결론적으로 stack에는 쌍을 찾지 못한 녀석들만 남게 된다 (..)

그래서 또 다시 조건문을 붙여서

 

6. stack 리스트가 비어있다면 YES (모두 쌍을 이루고 탈출하므로)

7. stack 리스트가 비어있지 않다면 NO를 출력한다.

 

---

 

Python code

python 코드로 작성하면 아래와 같다.

 

import sys
sys.stdin = open("test.txt", "r")

t = int(input())

for i in range(t):
    string = list(input())
    stack = []

    for bracket in string : 
        if bracket == '(' :
            stack.append(bracket)
        elif bracket == ')' and '(' in stack : 
            stack.pop()
        elif bracket == ')' and '(' not in stack : 
            stack.append(bracket)

    if not stack :
        print("YES")
    else :
        print("NO")

 

 

더 효율적인 코드가 분명히 존재한다... ㅠ