백준 3986 좋은단어 (C++)

* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다

백준 3986 좋은단어 입니다

 

문제 해석

이문제를 처음보았는데 저는 감이 정말로 안잡혔습니다

단어가 주어지면 그 단어에 단어 위로 아치형 곡선을 그어 같은 글자끼리 쌍을 지을수있다면 좋은단어 이고, 이 좋은단어의 개수를 세는 문제 인데 ABAB 와 같이 들어올때 어떻게 처리를 해야될지 감이 안잡혔습니다

 

 우선 예제중 AABB 를 보면 AA가 붙어 있고 BB가 붙어있습니다. 그래서 A는 A끼리, B는 B끼리 쌍을 짓을수있고, 곡선을 그어도 선이 교차하지 않습니다

AABB만 보게 되면 뭔가 감이 안잡힐수도있습니다, 이럴때 큰돌님이 주어진 문자열을 뒤집어 보고(BBAA), 한개 더 붙여보고(AABBAABB), 그리고 90도로 회전을 해보면 감이 잡힌다고 하셨습니다, 그러면 한번 90도로 회전을 시켜보면 아래와 같은 구조가 나옵니다

B
B
A
A

이러한 구조를 보고 좋은단어인지 알수있는 방법은 우선 처음에 A가 들어옵니다. 그리고 그 다음 A가 다시 들어옵니다

이때 만약 이전에 들어왔던 값이(A) 지금 들어온 값(A)과 같다면 해당 자료구조에 넣지 않고, 기존에 존재하는 자료구조에 있는 값도 삭제를 해주면됩니다, 마찬가지로 B같은경우도 B가 들어오고 다음 값으로 다시 B가 들어온다면 자료구조에 넣지않고, B를 삭제해주면됩니다

 

근데 만약 ABAB가 입력으로 들어오면 해당 자료구조에 A가 먼저 들어오고 B가 들어오게되는데 이전 값(A)과 현재값(B)가 서로 다르기때문에 삭제를 하지 않습니다

 

즉 같은 값이면 삭제를 하고, 아니면 값을 넣어주는것을 입력된 문자열 갯수만큼 반복을 하고, 반복이 끝나고 해당 자료구조에 크기가 0이라면 좋은단어라고 판단할수있습니다

 

여기서 이제 특정 자료구조가 나오는데 위에 자료구조는 '스택'입니다 스택은 후입선출(LIFO) 구조를 가지고있습니다 즉 스택에 A가 들어오고 스택에 가장 위에있는 값이랑 현재 들어오는 값을 비교하면서 진행하면은 해당 문제를 풀수있습니다

 

 

문제 풀이 순서

1. 단어의수(N) 과 좋은단어를 카운팅할 변수를 선언합니다

2. 단어를 입력 받을 문자열을 선업합니다

3. 단어의수를 입력받고, 단어의 순만큼 반복문을 돌립니다

4. 반복문을 돌리면서 단어를 입력받고 가장 중요한 스택을 선언해줍니다

5. 입력받은 문자열 만큼 다시 반복문을 돌립니다

6. 이때 만약 스택에 값이 하나라도 있고, 스택에 가장위에잇는 값이 현재 순회하고 있는 단어랑 같다면 스택에 가장 위에있는 값을 제거합니다

7. 만약 같이 않다면 스택에 값을 넣어둡니다

8. 문자열 반복이 끝나고 만약 스택에 크기가 0이라면 최종결과 카운트를 +1를 해줍니다

 

작성 코드

#include <bits/stdc++.h>
using namespace std;

//단어의수 n, 최종결과 ret 선언
int n,ret;

//단어 문자열 선언
string temp;

int main(){

    //단어의 수 입력
    cin >> n;

    //단어의 수 만큼 순회
    for(int i = 0; i < n; i++){

        //단어 입력 및 스택 선언
        cin >> temp;
        stack<char> stk;

        //입력받은 단어의 수 만큼 순회
        for(int j = 0; j < temp.size(); j++){

            //만약 스택에 값이 있고, 스택에 가장 위에있는 감이 순회하는 단어랑 같다면
            if(stk.size() && stk.top() == temp[j]){
                //스택에 가장 위에있는 값을 제거
                stk.pop();
            }else{
                //아니면 그 단어를 스택에 넣기 
                stk.push(temp[j]);
            }
        }

        //만약 스택 사이즈가 0이라면 최종결과 카운트
        if(stk.size() == 0){
            ret++;
        }

    }
    cout << ret << "\n";


    return 0;
}