[백준 3986] 좋은 단어

3986번: 좋은 단어

알고리즘 : 스택

난이도 : 실버Ⅳ

 

1. 문제요약

• A와 B로 이루어진 문자열이 여러개 주어지는데, 각 문자열에서 A끼리 및 B끼리 선을 이어주며 짝을 지을때, 선끼리 교차되지 않고 모든 문자를 짝지을 수 있는 문자열(ex AABB, ABBA 등)의 개수를 세는 문제이다.
• 시간제한은 1초이고 모든 문자열의 길이의 합은 최대 1,000,000이므로 시간복잡도가 $O(n^2)$가 되지 않도록 유의한다.

2. 구현과정

• 스택으로 구현할 것이다. 문자열들의 개수 N을 입력으로 받고, for문으로 N만큼 반복하면서 문자열을 ABstring에 입력으로 받아 시작한다.
• ABstring을 순회하면서 스택의 탑에 있는 문자와 동일하다면 스택을 팝해주고, 스택이 비었거나 탑에 있는 문자와 다르다면 스택에 푸쉬해 준다.
• 순회를 마쳤을때 스택이 비어있다면 좋은 단어에 해당한다.

3. 파이썬 코드

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
answer = 0
for _ in range(N):
    ABstring = input()
    stack = []
    for chr in ABstring:
        if stack and chr == stack[-1]:
            stack.pop()
        else:
            stack.append(chr)
    if not stack:
        answer += 1
print(answer)