백준 1342 행운의 문자열 C++

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

1342번: 행운의 문자열

---

문제

민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.

---

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다.

---

출력

첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다.

---

next_permutation을 이용해 해결했습니다.

aabbbaa

이런 입력이 주어진다면

먼저 문자 벡터에 문자열의 원소를 모두 넣어주었습니다. 그 후 n을 문자열의 길이로 초기화를 하고,

문자 벡터를 먼저 정렬 시켜주었습니다.(next_permutation 쓰기 위해서)

void input(){
    
    cin >> str;
    for(int i = 0;i<str.size();i++){
        v.push_back(str[i]);
    }
    n = str.size();
    sort(v.begin(),v.end());
}

 

그 후 permutation을 돌리는데 인접한 문자가 같지 않은 경우에만 cnt변수를 증가시켰습니다.!

void dfs(){
    do{
        bool flag = false;
        string new_ = "";
        for(int i = 0;i<n;i++){
            if(v[i] == v[i-1] || v[i] == v[i+1]){
                flag = true;
                break;
            }
            new_ += v[i];
        }
        if(flag == false){
            
            cnt++;
        }
        
    }while(next_permutation(v.begin(),v.end()));    
}

 

전체 소스 코드->

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int cnt = 0;
vector<char> v;
vector<char> combinate;
bool visited[11];
string str;
int n;

void input(){
    
    cin >> str;
    for(int i = 0;i<str.size();i++){
        v.push_back(str[i]);
    }
    n = str.size();
    sort(v.begin(),v.end());
}

void dfs(){
    do{
        bool flag = false;
        string new_ = "";
        for(int i = 0;i<n;i++){
            if(v[i] == v[i-1] || v[i] == v[i+1]){
                flag = true;
                break;
            }
            new_ += v[i];
        }
        if(flag == false){
            cout << new_ << '\n';
            cnt++;
        }
        
    }while(next_permutation(v.begin(),v.end()));    
}


int main(void){
    input();
    dfs();
    cout << cnt;
   
}