[ 백준 ] 3986 / 좋은 단어

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
53/228
post-thumbnail

# Appreciation

/*
 * Problem :: 3986 / 좋은 단어
 *
 * Kind :: Data Structure
 *
 * Insight
 * - ...ABA...
 *   ...BAB...
 *   처럼 교차하면 안된다
 *   + ...AA...
 *     ...BB...
 *     는 바로 쌍을 지어주자
 *     # 그러면 단어 앞에서부터 글자를 읽으면서
 *       AA or BB 면 없애주고
 *       마지막에 남은 문자열이 ABA... or BAB...
 *       이면 좋은 단어가 아니다!
 *       -> 마지막에 문자열이 비어있으면
 *          좋은 단어다!
 *
 * Point
 * - 가장 최근 글자를 알고 있어야 하니
 *   Stack 을 활용하자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <stack>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    string W[N];
    for (int i=0; i<N; i++)
        cin >> W[i];

    // Process
    int ans = 0;
    for (int i=0; i<N; i++) {
        stack<char> st;
        for (char c : W[i]) {
            /* c = 현재 글자
             * top = 스택에 쌓인 가장 최근 글자
             * st = 스택 */

            /* st 가 비어있거나 top 이 c 와 다르다면 */
            if (st.empty() || st.top() != c) {
                st.push(c); /* st 에 push */
            /* st 가 비어있지 않고 top 이 c 와 같다면 */
            } else {
                st.pop(); /* st 에서 pop */
            }
        }

        /* st 가 비어있으면 좋은 단어 */
        if (st.empty()) ans++;
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글