문제 3986

예시 입력 1

3
ABAB
AABB
ABBA

예시 출력 1

2

예시 입력 2

3
AAA
AA
AB

예시 출력 2

1

문제 이해

이 문제... 처음 봤을때는 어떻게 풀어야 하나 감이 오지 않았다. 고민해도 아이디어가 떠오르지 않아서 구글링을 하니까 비슷한 유형의 대표적인 문제로 프로그래머스의 "올바른 괄호"라는 문제가 있다고 한다. 그래서 그 문제부터 풀고, 바로 이전글에서 블로그로 남겨두었다.

올바른 괄호 문제
https://velog.io/@junseong/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Python-%EC%8A%A4%ED%83%9D%ED%81%90-%EC%98%AC%EB%B0%94%EB%A5%B8-%EA%B4%84%ED%98%B8

이 두 문제는 스택을 이용하는 대표적인 문제이다. 다만 다른점은 올바른 괄호가 되기 위해서는 반드시 괄호가 먼저 열리고, 닫혀야 한다. 닫히고 열리는 괄호는 올바르지 않기 때문이다. 하지만 "좋은 단어" 문제는 딱히 순서가 없다. 한 쌍의 곡선이 서로 교차하지 않으면 된다. 그 말은 즉, 한쌍의 문자 안에 교차 없이 쌍으로 존재해야 한다.

• 옳은 예시
  ABAABA -> 이런식으로 한 쌍안에서 다른 쌍을 품는 방식으로만 좋은 단어가 될 수 있다. 이렇게 배치되어야만 곡선이 교차하지 않기 때문이다.

• 틀린 예시
  ABABAA -> 이런 배치로는 천재를 데리고 와도 교차안하기 힘들다.

문자열 s에서 값을 하나씩 뽑아서 스택에 값을 하나씩 넣을 때, 현재 스택의 마지막 값과 스택에 넣을 값이 같으면 스택에서 마지막 값을 pop()해주면 된다.

문자열 ABAABA가 있다고 가정

1. 현재 스택에 값이 없으니 A(s[0])를 스택에 넣는다. stack = ["A"]

2. 현재 스택의 마지막 값인 A(s[-1])과 다음에 들어올 값인 B(s[1])이 다르므로 B(s[1])를 스택에 넣는다. stack = ["A", "B"]

3. 스택의 마지막 값인 B(s[-1])과 다음에 들어올 값인 A(s[2])가 다르므로 스택에 A를 넣는다. stack = ["A", "B", "A"]

4. 스택의 마지막 값인 A(s[-1])과 다음에 들어올 값인 A(s[3])가 같으므로 스택의 마지막 값인 A(s[-1])를 제거(pop()). stack = ["A", "B"]

5. 스택의 마지막 값인 B(s[-1])과 다음에 들어올 값인 B(s[4])가 같으므로 스택의 마지막 값인 B(s[-1])를 제거(pop()). stack = ["A"]

6. 스택의 마지막 값인 A(s[-1])과 다음에 들어올 값인 A(s[5])가 같으므로 스택의 마지막 값인 A(s[-1])를 제거(pop()). stack = []

7. 문자열을 모두 확인한 후에 스택이 비었으면 좋은 단어, 값이 있으면 안 좋은 단어이다.

내가 짠 코드

# BOJ 3986번 좋은 단어

n = int(input())

count = 0
for i in range(n):
    # 파이썬이니 스택 역할을 할 리스트 선언
    stack = []

    s = input()
    for value in s:
        if stack:
            if value == stack[-1]:
                stack.pop()
            else:
                stack.append(value)
        else:
            stack.append(value)
    
    if not stack:
        count += 1

print(count)

생각보다 코드가 간단하고, 문제 이해만 잘한다고 어렵지 않게 풀 수 있음. 근데 스택 문제나 비슷한 유형을 풀지 않은 사람에게는 문제 이해가 어려울 수 있는 문제라고 생각한다.