백준 3986번
https://www.acmicpc.net/problem/3986

문제

후기

⏰ 풀이시간 30분 ++⏰

위와 같이 A는 A끼리, B는 B끼리 연결했을 때, 선이 서로 겹치지 않는 단어는

좋은 단어고, 이 좋은 단어의 개수를 구하는 것이 문제의 요구다.

스택안에 알파벳을 추가하다가,

안에서 연속되는 알파벳이 나왔을 때, 해당 요소들을 pop 해준다.

만약 모든 요소가 pop 되지 않으면, 좋은 단어가 아니다

위와 같은 로직으로 문제를 구현하게 되었다.

나의 풀이

import sys
input= sys.stdin.readline

N= int(input()) #단어의 수
cnt = 0 #좋은 단어의수

# 한 알파벳이 나오고 다음 그 알파벳이 닫히기 전까지는 그 내부의 알파벳은 연속적으로 나와야된다.
# ex)  ABAABA ->  A가 나오고 B가 연속적으로 나와야하지만, 그 안에 있는 A가 연속적으로 나오기때문에, 그 A를 제거하면 B도 연속적으로 나왔다고 볼수있으므로 좋은단어다.
#이와 같은 알고리즘으로 구현
#스택 쓰면될듯..?

for _ in range(N):
    li = []
    word= str(input().strip())
    k= len(word)
    if k%2 !=0: #알파벳이 짝지어 지지 않으면, 좋은단어가 아니다.
        continue
    for i in range(k):
        if len(li)==0: #스택이 비었으면
            li.append(word[i]) #알파벳을 추가한다.
        else:
            if word[i]==li[-1]: #새로 들어오는 알파벳이, 스택안에 들어있는 마지막 알파벳과 같다면
               li.pop() # 새로 들어오는 알파벳을 넣을필요없이, 스택안에 들어있는 마지막 알파벳 pop
            else:
                li.append(word[i])
    if len(li)==0: #최종적으로 스택이 비어있어야
        cnt+=1 #좋은단어
print(cnt)