백준 1342번 C++

https://www.acmicpc.net/problem/1342

1342번: 행운의 문자열

보자마자 생각난 것 : color graph! 알고리즘 수업 열심히 들은 보람이 있다고 생각했다 ㅋㅋㅋ
교수님 보고 계십니까?!! 앞으로 엘베에서 마주치면 90도로 인사박겠습니다!!!
하하
암튼 나한테 휴학은 없으니까 내년 그니까 3학년 1학기 시험기간이 돌아올 때 까지 1일 1백준 다시 레츄고
애들아 열심히 하자...

 

생각

행운의 문자열인지 확인하는 방법 (Find 함수로 따로 만들자!)
1. 인접한 문자가 같은지/같지 않은지 확인
2. 문자열의 인덱스를 1씩 증가해가면서 확인하다가 틀리면 false return하기
3. 인덱스 끝까지 맞으면 count 증가

재배치 하는 방법(함수 따로 안만들고 main에서 dfs로 전부 바꾸면 될 듯?)
1. 하... 어떻게 하지 주어진 문자열에서 나올 수 있는 모든 문자열 찾기! >>> 순열 구현하기
2. 순열이라 어쩔 수 없이 중복이 발생하는데 이걸 어떻게 처리할 것인가 고민해보기

 

or 한 번에 처리하는 방법...!!!
1. 입력받은 문자열을 기록해둔다
2. 기록해둔 알파벳을 하나씩 넣으면서 새로운 문자열을 만들어준다! (이 단계에서 무조건 다른 알파벳을 뒤에 붙이기 때문에!! 행운의 문자열 판단도 동시에 가능함)

#include <iostream>
#include <algorithm>
using namespace std;

bool check(string &s){
    for (int i = 0; i < s.length() - 1; i++){
        if (s[i] == s[i + 1]){
            return false;
        }
    }
    return true;
}

int find(string& s){
    string temp = s;
    sort(temp.begin(), temp.end());

    int count = 0;

    do{
        if (check(temp)){
            count++;
        }
    } while (next_permutation(temp.begin(), temp.end()));
    return count;
}

int main(){
    string s;
    cin >> s;
    int result = find(s);
    cout << result;
}