[ 백준 ] 2607 / 비슷한 단어

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
38/228
post-thumbnail
post-custom-banner

# Appreciation

/*
 * Problem :: 2670 / 비슷한 단어
 *
 * Kind :: Simulation
 *
 * Insight
 * - Python 의 Counter 느낌이다
 *   단어 A 와 B 가 있을 때
 *   각 단어를 글자별로 나누어서 그 단어의 구성을 알아내고
 *   단어끼리 구성을 비교해서 비슷한 단어인지 판단한다
 *   + DOG = 'D', 'O', 'G'
 *     GOD = 'G', 'O', 'D'
 *     # 위 두 단어는 같은 구성을 갖는다
 *   + GOD = 'G', 'O', 'D'
 *     GOOD = 'G', 'O', 'O', 'D'
 *     # 위 두 단어는 다른 구성을 갖는다
 *       그러나 GOD 에 'O' 를 추가하면 같은 구성을 가지게 된다
 *   + GOD = 'G', 'O', 'D'
 *     DOLL = 'D', 'O', 'L', 'L'
 *     # 위 두 단어는 다른 구성을 갖는다
 *       또한 한 단어에서 한 문자를 더하거나 빼거나 다른 문자로 바꾸어도
 *       같은 구성을 가질 수 없다
 *       -> Python 의 Counter 느낌은
 *          C++ 의 multiset 으로 흉내내면 될 듯 하다
 *          => GOD - DOLL = 'G'
 *             DOLL - GOD = 'L', 'L'
 *             한 문자를 더하거나 빼거나 다른 문자로 바꾸어도
 *             같은 구성을 만들 수 없다
 *
 *             즉, 단어 A 와 B 가 있을 때
 *             multiset(A) - multiset(B) = A-B
 *             multiset(B) - multiset(A) = B-A
 *             라고 할 때,
 *             n(A-B) <= 1 그리고 n(B-A) <= 1 때만
 *             비슷한 단어를 만들 수 있다!
 *
 *             n(A-B) | n(B-A) = DESC
 *                0   |    0   = 같은 구성
 *                0   |    1   = A 에 한 문자 추가하면 같은 구성
 *                1   |    0   = B 에 한 문자 추가하면 같은 구성
 *                1   |    1   = A 또는 B 에서 한 문자 바꾸면 같은 구성
 */

# Code

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

#include <iostream>
#include <set>
#include <algorithm>

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
    /* 첫 번째 단어 multiset */
    multiset<char> fs(W[0].begin(), W[0].end());

    int ans = 0;
    for (int i=1; i<N; i++) {
        /* i > 0 번째 단어 multiset */
        multiset<char> is(W[i].begin(), W[i].end());

        multiset<char> f_is, i_fs; /* fs - is, is - fs */
        set_difference(fs.begin(), fs.end(), is.begin(), is.end(),
                       inserter(f_is, f_is.begin()));
        set_difference(is.begin(), is.end(), fs.begin(), fs.end(),
                       inserter(i_fs, i_fs.begin()));

        /* n(fs-is) <= 1 이고 n(is-fs) <= 1 이어야만 비슷한 단어 */
        if (f_is.size() <= 1 && i_fs.size() <= 1) ans++;
    }

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

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

0개의 댓글