[백준 3986] 좋은 단어 - c++로 구현한 스택 (해설 O)

문제 개요

• 문제 번호: 3986
• 제목: 좋은단어
• 난이도: 실버 4
• 링크: 백준 3986번

---

문제 설명

같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓는다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 좋은단어의 갯수를 찾는 문제

선을 그었을 때 교차하지 않으면 좋은 단어이다.

선을 그었을 때 교차하면 좋은 단어가 아니다.

---

접근 방법

1. 단어를 순회한다
2. 스택이 비어있다면 push
3. 지금 단어가 스택의 top에 있는 문자와 같다면 pop
4. 모든 조건이 다르다면 push
5. 단어 순회가 끝났는데 스택이 비어있다면 좋은단어

---

구현 코드

#include<iostream>
#include<stack>
#define endl "\n"

using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    int n, ans = 0;

    cin >> n;
    cin.ignore();

    while (n--)
    {
        stack<char> s;

        string word;
        getline(cin, word);

        for(auto c : word){
            if(s.empty()){
                s.push(c);
            }
            else if(c == 'A' && s.top() == 'A'){
                s.pop();
            }
            else if(c == 'B' && s.top() == 'B'){
                 s.pop();
            }
            else{
                s.push(c);
            }
        }

        if(s.empty()) ans++;
    }

    cout << ans << endl;
}

---

시간 복잡도

• O(N): N은 단어의 길이

---

어려웠던 점

1. 문제를 이해하는게 어려웠다 아치모양으로 그엇다는 말이 이해가 너무 안갔었다.
2. getline을 사용할떄 주의점은 이전 입력을 받았을때 \n이 입력으로 들어온다. 그래서 입력을 무시하는 cin.ignore()를 사용해야한다.