[백준] 행운의 문자열 (1342번)

문제

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

입력

첫째 줄에 문자열 S가 주어진다. 길이는 최대 10이다.

출력

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

예제 입력 1 복사

aabbbaa

예제 출력 1 복사

1

---

행운의 문자열을 최대한 만드는 문제이다.

행운의 문자열이란 인접한 문자가 다른 문자인 문자열이다. 예를들어 bab는 가능하지만 bba는 불가능하다.

 

우선 입력을 받으면 각 알파벳이 몇 개 있는지 기록한다.

dfs를 통해 남아있는 알파벳을 한 개 씩 넣으며, 문자열의 가장 뒤에 있는 문자와 다른 문자만 넣어준다.

원본 문자열의 길이만큼 문자열을 만들었으면 결과값을 1 증가하고 종료하면 된다.

 

처음엔 중복이 나오지 않을까 하는 생각에 map을 이용해 기록했지만 메모리 초과가 떴다.

생각해보니 중복이 나오지 않는다. 

각 단계에서 알파벳 별로 한 개 씩만 추가하기 때문에 중복이 생기지 않는다. 

 

예를 들어 aab가 원본 문자열이면 dfs는 각각 

a -> ab -> aba (O)

b -> ba -> baa (X) 이렇게 두 단계만 실행되기 때문이다. a - ab - aba와 a - ab - aba를 두번 실행하는 것 처럼 문자를 다시 추가하지않는다.

따라서 dfs를 이용한 풀이로 해결이 가능하다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%96%89%EC%9A%B4%EC%9D%98%20%EB%AC%B8%EC%9E%90%EC%97%B4%20(1342%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string origin;
int res;
int p[27];

void dfs(int idx, string cur) {

	if (idx == origin.size()) {
		res++;
		return;
	}

	for (int i = 0; i < 26; i++) {
		if (p[i] == 0) continue;
		if (cur != "" && cur[cur.size() - 1] == (char)('a' + i)) continue;
		p[i]--;
		dfs(idx + 1, cur + (char)('a' + i));
		p[i]++;
	}
}

int main()
{
	cin >> origin;
	for (int i = 0; i < origin.size(); i++)
		p[origin[i] - 'a']++;
	
	dfs(0, "");

	cout << res;
}