[백준] 3986 좋은 단어

문제 설명

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

3986번: 좋은 단어

단어위로 아치형 곡선을 그려 같은 글자끼리 쌍을 짓기로 했을 때, 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치와 짝을 지을 수 있는 '좋은 단어'의 수 구하기

 

문제 풀이법

좋은 단어란 AABB, ABBA처럼 짝을 지을 수 있는 단어이다

ABAB같은 경우에는 아치형 곡선을 그렸을 때, 선이 교차하므로 좋은 단어가 아니다

 

따라서 stack을 사용하면 된다

• 만일 단어가 A인 경우
  • 스택이 비어있으면 A를 push
  • 스택이 비어있지 않고, stack의 top이 A이면 pop
  • 스택이 비어있지 않고, stack의 top이 A가 아니면 A를 push
• 만일 단어가 B인 경우
  • 스택이 비어있으면 B를 push
  • 스택이 비어있지 않고, stack의 top이 B이면 pop
  • 스택이 비어있지 않고, stack의 top이 B가 아니면 B를 push

 

작업이 끝난 후, stack이 비어있다면 좋은 단어이고, 비어있지 않다면 좋은 단어가 아니다

 

소스 코드

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int sum = 0;
    while (n > 0)
    {
        string str;
        cin >> str;
        
        stack<char> s;
        for (int i = 0; i < str.size(); i++)
        {
            if (str[i] == 'A')
            {
                if (s.empty())
                    s.push('A');
                else
                {
                    if (s.top() == 'A')
                        s.pop();
                    else
                        s.push('A');
                        
                }
            }
            else if (str[i] == 'B')
            {
                if (s.empty())
                    s.push('B');
                else
                {
                    if (s.top() == 'B')
                        s.pop();
                    else
                        s.push('B');
                        
                }
            }
        }
        
        if (s.empty())
            sum++;
        n--;
    }

    printf("%d\n", sum);
    return 0;
}