위 문제는 대표적인 Stack 을 사용해야하는 유형이다.

짝짓기, 교차하지 않도록, 문자열 삭제..등등의 키워드가 등장하면 대부분 stack 을 활용하여 쉽게 풀 수 있다.

일단 문제를 파악해보자.

(1) 같은 글자간의 연결선이 교차하지 않으려면 최대한 연속인 애들끼리 연결되어야한다. + 연속된 애들끼리 연결되는 경우는 그냥 세트로 없는걸로 봐도된다.
-> stack에 쌓으면서 같은게 2개 연속되면 pop() 해버리고, 최종 stack의 사이즈가 1이면 짝짓기 실패, 사이즈가 0이면 짝짓기 성공으로 판정하면 어떨까?
-> 이를 테케에 적용해보면 모두 성립하는 것을 확인할 수 있다.

1. 풀이

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    string word;
    int ret = n;
    while(n--) {
        cin >> word;
        stack<char> stk; //이렇게하면 stack이 어떻게 초기화될까
        for(char &c: word) {
            if(stk.size() && stk.top()==c) stk.pop();
            else stk.push(c);
        }
        if(stk.size()!=0) ret--; 
    }
    cout << ret;
    return 0;
}

시간복잡도는 O(n*s) (s는 단어의 길이를 의미) 이다.

n<=100, s <=100000 이므로 연산량은 10000000=1천만 정도로 안전하다

2. 오답노트

(1) 문제 키워드로 stack 생각해내기

• 문제에 짝짓기, 교차하지 않도록, 문자열 삭제..등등의 키워드가 등장하면 대부분 stack 을 활용하여 쉽게 풀 수 있음을 잊지말자.
• 또한 stack으로 풀기위하여 문제에서 주어진 입력을 90도 회전시켜서 봐야한다.

위의 2가지 꿀팁들을 잊지말자 !

(2) stack 사용 미숙

아직 C++의 stack 사용이 미숙하다. 관련하여 개념을 조만간 복습해야겠다.