문제 푼 날짜 : 2021-12-02

문제

문제 링크 : https://www.acmicpc.net/problem/1342

접근 및 풀이

순열을 이용하면 간단히 풀 수 있는 문제였다.
C++의 next_permutation 함수를 이용하여 문자열의 모든 경우의 수를 구해주었고, 그 때마다 문자열의 각 자리 양 옆의 문자가 같은지 체크해주었다.

코드

// 백준 1342번 : 행운의 문자열
#include <bits/stdc++.h>

using namespace std;

int ans;
string str;

bool isValid() {
    for (int i = 1; i < str.length() - 1; i++) {
        char ch = str[i];
        if (str[i - 1] == ch || str[i + 1] == ch) {
            return false;
        }
    }
    return true;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> str;

    sort(str.begin(), str.end());
    do {
        if (isValid()) {
            ans++;
        }
    } while (next_permutation(str.begin(), str.end()));

    cout << ans;
    return 0;
}

결과

피드백

next_permutation으로 완전탐색을 할 경우 sort는 필수!