[BOJ/Silver 1] 백준 1342 행운의 문자열(C++)

문제 링크

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

 

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

aabbbaa

예제 출력 1

1

예제 입력 2

ab

예제 출력 2

2

예제 입력 3

aaab

예제 출력 3

0

예제 입력 4

abcdefghij

예제 출력 4

3628800

 

알고리즘 분류

• 백트래킹

 

풀이

next_permutation()을 사용해서 문자열 S를 재배치하는 최대 10!가지의 경우의 수를 탐색한다.

문자열 S를 재배치하고, 재배치한 문자열이 행운의 문자열인지를 파악한다. 이 때에도 최대 9번의 연산을 하게 되므로 총 연산 횟수는 10! × 9번이 된다.

이렇게 최대 10!가지의 문자열 중 행운의 문자열의 개수를 파악한다.

처음에는 행운의 문자열들을 set에 추가하도록 했는데, 생각해보니 그럴 필요가 없는 것이 찾는 행운의 문자열은 인접한 알파벳들이 모두 달라야 하기 때문에, 전부 다른 문자열이 될 것이고 set에 추가한다고 해도 그만큼의 시간과 메모리를 추가로 사용해야 한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 11
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
string S;
bool Visited[MAX];
int Answer;

void input() {
	cin >> S;
}

void settings() {
	sort(S.begin(), S.end());

	do {
		bool Flag = true;
		for (int i = 1; i < (int)S.length(); i++) {
			if (S[i - 1] == S[i]) {
				Flag = false;
				break;
			}
		}
		if (Flag) Answer++;
	} while (next_permutation(S.begin(), S.end()));
}

void printAnswer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO

	input();
	settings();
	printAnswer();

	return 0;
}