[백준] 3986 파이썬(python) : 좋은 단어

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

3986번: 좋은 단어

 

 

처음에 문제를 볼때 이걸 어떻게 스택으로 풀 수 있지 생각했는데 이전에 풀었던 괄호 짝 맞추기 문제들 처럼 같은 알파벳끼리 짝을 맞춰주면 풀 수 있다. 문제에서는 아치형 곡선이라고 말했는데 여는 괄호를 닫는 괄호와 짝이 맞는지로 바꿀 수 있다.

ABAB는 3번째 위치의 A가 들어올 때 stack[-1]이 A가 아니므로 좋은 단어가 아니다.

AABB는 2번째 위치의 A가 들어올 때 stack[-1]가 A이므로 stack.pop()을 해서 지워주고 3번째 위치의 B가 들어올 때 stack[-1]이 B이므로 stack.pop()을 해서 지워주면 len(stack) == 0이므로 좋은 단어가 된다.

ABBA도 AA도 같이 좋은 단어가 되고 AAA는 3번째 위치의 A가 남게 되므로 좋은 단어가 아니다.

 

import sys
n = int(sys.stdin.readline())
cnt = 0
for _ in range(n):
    string = sys.stdin.readline().rstrip()
    stack = []
    for char in string:
        if len(stack) != 0 and stack[-1] == char: #1
            stack.pop()
        else: #2
            stack.append(char)
    if len(stack) == 0: #3
        cnt += 1
print(cnt)

 

#1 : 길이가 0이 아니고 stack의 top이 입력값의 요소와 일치하므로 stack.pop() 수행

#2 : 처음이라면 열린괄호처럼 stack에 삽입

#3 : 모든 과정이 끝나고 길이가 0이면 좋은 단어이므로 cnt +1