2022-07-02-good-word-3986

• toc {:toc}

문제

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던

평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1 시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서

보고서의 모든 글자가 A 와 B 로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 ’ 좋은 단어 ’ 나 세보기로 마음

먹었다.

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리 (A 는 A 끼리, B 는 B 끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지

않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 ’ 좋은 단어 ’ 이다. 평석이가

’ 좋은 단어 ’ 개수를 세는 것을 도와주자.

입력

첫째 줄에 단어의 수 N 이 주어진다. (1 ≤ N ≤ 100)

다음 N 개 줄에는 A 와 B 로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2 와 100,000 사이이며, 모든 단어 길이의 합은 1,000,000 을 넘지 않는다.

출력

첫째 줄에 좋은 단어의 수를 출력한다.

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

풀이

A, B 의 숫자를 세어 같으면 스택에서 pop 되도록 하고 아니면 집어넣고 마지막에 참, 거짓 판단

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, cntA, cntB, sum = 0;
    bool isOK = true;
    cin >> n;
    while(n--){
        string str;
        cin >> str;
        stack<char> s;
        cntA = cntB = 0;            // 초기화
        isOK = true화
        for(char c : str){
            if(s.empty()){          // 스택이 비었을 때 처리
                if(c == 'A') cntA++;
                else cntB++;
                s.push(c);
            }
            else{                   // 스택이 비어있지 않을 때
                if(s.top() == c){   // 같을 때 pair로 묶어서 pop
                    if(c == 'A') cntA--;
                    else cntB--;
                    s.pop();
                }
                else{               // 같지 않으면 스택에 넣어줌
                    if(c == 'A'){
                        cntA++;
                        s.push(c);
                    }
                    else if(c == 'B'){
                        cntB++;
                        s.push(c);
                    }
                        
                }
            }
        }
        if(s.empty() && cntA == 0 && cntB == 0) sum++; // 참, 거짓 판단
    }
    cout << sum << endl;
    return 0;
}