BaekJoon 1342 행운의 문자열

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

소스결과 1984 KB / 260 ms

출처 Baekjoon

언어 C++ 17

분류 백트래킹 탐색

 

설명

문자열 S의 문자를 재 배치 하였을 때 모든 문자가 인접한 문자와 같지 않은 문자열의 개수를 찾는 문제

 

문자열을 재 배치 할 때 현재 위치를 기준으로 양옆을 생각하지 않고 이전 문자가 무엇 이었는지만 기억 하면 된다.

문자열을 진짜로 재 배치 한다는 생각보다 앞자리부터 하나씩 문자를 넣어 간다는 점이면 충분하다.

백트래킹을 연습하기에는 괜찮은 문제

 

문제 조건에서는 문자열의 범위가 주어지지 않지만 테스트 케이스로 주어지는 문자는 알파벳 소문자에 한정되었다.

 

알고리즘

1. 주어진 문자열의 각 알파벳의 개수를 저장한다.

2. 0번 인덱스부터 재귀호출로 이전 문자의 값과 일치하지 않는 알파벳 중 개수가 0이 아닌 알파벳을 현재 위치의 알파벳으로 처리한다.

3. 처리하는 인덱스가 마지막 위치까지 도달한다면 행운의 문자열로 간주하고 개수를 1 늘린다.

4. 출력

 

소스코드

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

using namespace std;

const short MAX = 10;
const short ALPHA_MAX = 26;
int inputLength;
int alpha[ALPHA_MAX];

int solve(char before, int pos)
{
	int count = 0;

	if (pos == inputLength)
		++count;
	else
	{
		for (int i = 0; i < ALPHA_MAX; i++)
		{
			if (alpha[i] < 1 || 'a' + i == before)
				continue;
			
			--alpha[i];
			count += solve('a' + i, pos + 1);
			++alpha[i];
		}
	}

	return count;
}

int main()
{
	char input[MAX + 1] = { };

	cin >> input;

	inputLength = strlen(input);

	for (int i = 0; i < inputLength; i++)
		alpha[input[i] - 'a']++;

	cout << solve(0, 0);

	return 0;
}