[알고리즘][Python] 백준(BOJ) 3986 좋은 단어_파이썬

 

3986 좋은 단어    www.acmicpc.net/problem/3986

3986번: 좋은 단어

 

 

 

문제 풀기 전 공부할 것 : 자료 구조, 스택

 

 

 

 

 

 

 

풀이

<내용>

• 좋은 단어를 찾는 방법을 괄호가 바로 되어 있는지로 해석했다.
• 따라서 단어를 pop 하면서 하나씩 꺼내고 stk가 비어있으면 pop한 글자를 넣고
• stk가 비어있지 않으면 stk의 마지막 단어와 비교하여 같으면 stk에서 그 글자를 빼고 아니면 stk에 글자를 넣는 방식으로 진행한다.
• stk에 글자가 들어있으면 좋은 단어가 아니다.

 

 

 

<코드>

import sys
input = sys.stdin.readline

n = int(input())
words = [list(input().rstrip()) for _ in range(n)]
cnt = 0
for word in words:
    stk = []
    while word:
        w = word.pop()
        if not stk:
            stk.append(w)
        else:
            if stk[-1] == w:
                stk.pop()
            else:
                stk.append(w)
                
    if not stk:
        cnt += 1
print(cnt)