[Python] 3986: 좋은 단어

 

 

문제 링크

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

 

 

 

선이 교차하지 않아야 한다는 조건만 정확하게 파악한다면 쉽게 풀 수 있는 문제다.

 

1. 연속된 문자들을 제거하고 봤을 때도 연속된 문자가 있어야 한다.

2. 문자가 끝났을 때 쌍을 이루지 못하는 문자가 남아있으면 안 된다.

 

Stack을 이용해서 첫 문자 또는 연속하지 않는 문자를 push해주고, 연속되면 pop으로 빼주면 되는 쉬운 문제가 된다.

n = int(input())
cnt = 0

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

    for i in str:
        if not len(stack):  # 스택이 비었으면 추가
            stack.append(i)
        elif stack[-1] == i:  # 같은 문자가 연속되면 제거
            stack.pop(-1)
        else:
            stack.append(i)  # 다르면 스택에 추가

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

print(cnt)

 

해보진 않았지만 2번째 if문의 경우 아마 str에서 직전 문자를 직접 비교해도 상관 없긴할 것이다.