[백준 1342 - C++] 행운의 문자열

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

1342번: 행운의 문자열

문제

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

 

입력

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

 

출력

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

 

예제 입력 1 

aabbbaa

예제 출력 1 

1

 

풀이

이 문제에선 문자열의 최대길이가 10으로 다소 작기 때문에 모든 경우를 다 확인해도 시간초과가 나지않는다.

이 때 서로 다른 문자열의 개수만 남게 중복을 어떻게 제거할지가 고민이었는데, 그냥 중복되는 횟수를 구해서 나눠주면 된다.

 

예를 들어 aabb의 경우

중복을 무시하기 위해 편의상 a1 a2 b1 b2라고 하겠다.

aabb : a1a2b1b2 / a1a2b2b1 / a2a1b1b2 / a2a1b2b1 =>4가지

abab 역시 4가지

bbaa 역시 4가지

baba 역시 4가지로 나타나게 된다.

그리고 이중 행운의 문자열은 abab, baba => 8가지 이다.

이러한 중복을 제거하기 위해서는 (a의 개수)! * (b의 개수)! 로 나눠주어야한다.

즉, 서로다른 행운의 문자열은 8 / 2! * 2! = 8 / 4 = 2개 이다.

 

#include <iostream>
#include <cstdio>
#include <string.h>

char inArr[11];
char newArr[11];
int check[11];
int dupli[26];
int lenArr;
int result;

void checkLuck(){
    for(int i=0; i<lenArr-1; i++){
        if(newArr[i]==newArr[i+1])
            return;
    }
    result++;
}

void dfs(int cnt){
    if(cnt == lenArr){
        checkLuck();
        //printf("a\n");
        return;
    }
    
    for(int i=0; i<lenArr; i++){
        if(check[i])
            continue;
        newArr[cnt] = inArr[i];
        check[i] = 1;
        dfs(cnt+1);
        check[i] = 0;
    }
}

int main() {
    
    int dup_num=1;
    
    scanf("%s", inArr);
    lenArr = strlen(inArr);
    
    //한글자씩 추가해 전부 확인
    for(int i=0; i<lenArr; i++){
        newArr[0] = inArr[i];
        check[i] = 1;
        dfs(1);
        check[i] = 0;
    }
    
    //중복되는 알파벳있는 경우 각각이 몇번 나오는지
    for(int i=0; i<lenArr; i++)
        dupli[inArr[i]-'a']++;
    
    //중복제거를 위해 나눠줄 값 연산
    for(int i=0; i<26; i++){
        for(int j=2; j<=dupli[i]; j++)
            dup_num *= j;
    }
    
    printf("%d\n", result/dup_num);
}