[백준/Python] 3986번: 좋은 단어

문제

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자. 이 때 단어는 A또는 B로 이루어져 있다.

입력

첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

풀이

스택을 이용한다. 단어의 왼쪽부터 시작해서 A바로 옆에 B가 있거나, B바로 옆에 A가 있으면 좋은 단어일 수 없기 때문에, 단어의 왼쪽부터 스택에 추가하면서 조건에 따라 스택에 글자를 더할지 뺄지 결정하고, 다 끝난 뒤에는 스택이 비어있는지 여부를 통해 좋은 단어인지 알 수 있다. 

또한 단어의 길이가 홀수이면 짝이 맞을 수 없으므로 처음부터 배제할 수 있다.

코드

n = int(input())
cnt = 0

for _ in range(n):
    arr = input()
    stack = []

    if len(arr) % 2 == 1: # 길이가 홀수이면 좋은 단어가 될 수 없음
        continue

    for char in arr:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)

    # 스택이 비어 있으면 좋은 단어임
    if not stack:
        cnt += 1
    
print(cnt)