[ 백준 ] 1342 / 행운의 문자열

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

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

# Appreciation

/*
 * Problem :: 1342 / 행운의 문자열
 *
 * Kind :: Brute Force
 *
 * Insight
 * - max(len(S))=10
 *   10! = 3628800
 *   + 다해봐도 되겠네...?
 *     문자열을 정렬하고
 *     next_permutation 쓰면
 *     모든 문자열을 탐색할 수 있겠다...!
 *
 * Point
 * - 이웃해 있는 지는 unique 써서 검사하자
 *   + unique(aaabbccc) -> abc
 */

# Code

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

#include <iostream>
#include <algorithm>
#include <functional>

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
    string S; cin >> S;

    // Process
    /* 행운의 문자열 판별 함수 */
    function<bool(string)> isFortune = [](string s) {
        string u = s;
        /* 문자열 s 에 unique 적용 */
        u.erase(unique(u.begin(), u.end()), u.end());
        return s == u; /* s 와 u 가 같다면 s 는 이웃한 문자가 모두 다름을 뜻함 */
    };

    sort(S.begin(), S.end()); /* 문자열 s 정렬 */
    int ans = 0;
    do {
        if (isFortune(S)) ans++;
      /* next_permutation 으로 재배치 가능한 모든 문자열 탐색 */
    } while (next_permutation(S.begin(), S.end()));

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

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

0개의 댓글