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

문제

3986번: 좋은 단어

알고리즘

- 단어의 수만큼 반복하여 단어를 확인한다.

- 반복문을 통해 입력받은 단어의 문자열을 확인한다.

- 스택 구조를 이용하여 스택의 마지막 요소와 현재 탐색하고 있는 요소가 같으면 아치형이 되므로 스택의 마지막 요소를 팝해준다.

- 그렇지 않다면 스택에 추가한다.

- 반복문을 끝내구 스택의 길이가 1이면 아치형으로 모두 연결된 것으로 좋은 단어이다.

- 스택에 길이가 1인 이유는 처음에 스택에 0을 넣었기 때문이다.

코드

import sys

n = int(sys.stdin.readline())
res = []

# 단어의 수만큼 반복하면 단어를 확인
for _ in range(n):
    s = list(map(str, sys.stdin.readline().strip()))
    stack = [0]
    # 반복문으로 문자열을 확인
    for i in s:
        # 스택의 마지막 요소와 현재 탐색하고 있는 요소와 같으면
        # 팝해준다.
        if stack[-1] == i:
            stack.pop()
        # 그렇지 않다면 스택에 추가한다.
        else:
            stack.append(i)

    # 스택에 길이가 1이면 아치형으로 모두 연결된 것으로 좋은 단어이다.
    # 처음에 스택에 0을 넣었기 때문에 길이가 1
    if len(stack) == 1:
        res.append(1)

print(len(res))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법