백준 3986 좋은 단어

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

문제

• N개 줄에는 A와 B로만 이루어진 단어가 주어진다.
• 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓는다. 이때 글자 1개 당 하나의 곡선만 그을 수 있다.
• 만약 선끼리 교차하지 않으면서 모든 글자를 짝 지을수 있다면 '좋은 단어'다.
• 주어진 N개의 단어 중 '좋은 단어'의 개수를 구한다.

나의 풀이

• 이 문제 풀이에 필요한 기본 원칙은 같은 글자 중 서로 완전히 접한 글자 부터 연결해야한다.
• 위의 원칙을 구현하는 가장 좋은 방법은 stack 이다.

import sys
import collections

n = int(sys.stdin.readline().strip())

cnt=0
q = collections.deque()
for _ in range(n):
    input=sys.stdin.readline().strip()
    for s in input:
        if len(q) ==0:
            q.append(s)    
        elif q[-1] ==s:
            q.pop()
        else:
            q.append(s)
        
    if len(q) ==0: #좋은 단어 성공일 경우 cnt + 1
        cnt+=1 
        q.clear()
    else:
        q.clear()
    

print(cnt)

오답노트

• 원칙을 생각해내지 못해서 시간을 많이 빼았겼음. 
• 아직도 왜 저 원칙이 적용되는지 완벽히 이해는 안됨.여러번 봐야할 듯