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

문제

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

입력

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

출력

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

예제 입력 1 

aabbbaa

예제 출력 1 

1

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

using namespace std;

vector<string> result;

void process(string remain, char prev, string s)
{
	/* 
	If the remain is empty, 
	it means that we succeeded in creating a string that
	satisfies the conditions in question.
	*/
	if(remain == "" && s != "") {
		result.push_back(s);
		return ;
	}
	
	/* 
	Choose one charter from the remain except the same as prev.
	And then call 'process' recursively.
	*/
	for(int i=0; i<remain.size(); ++i) {
		if(prev != remain[i]) {
			string _remain = remain;
			string _s = s;
			_remain.erase(_remain.begin()+i);
			_s.push_back(remain[i]);
			process(_remain, remain[i], _s);
		}
	}
}

int main(void)
{
	string str = "";
	cin >> str;
	
	process(str,' ',string(""));
	
	vector<string>::iterator it;
	
	/* 
	'unique' eliminates the same among the adjacent ones.
	So before the call unique func, we should sort it 
	*/
	sort(result.begin(), result.end());
	it = unique(result.begin(), result.end());
	
	/* 
	'unique' pushes the same things back to the end without actually erasing them.
	*/
	result.erase(it, result.end());
	
	cout << result.size() << endl;
	
	return 0;
}

더 효율적인 풀이가 있을 거 같은데, 우선은 제일 먼저 생각나는 풀이로 풀었다.

빈 문자열(s)에서 시작해서, 주어진 문자열(remain)로부터 문자를 하나씩 골라가는 방식이다.

문제에 주어진대로, 문자를 고를 때는 앞에 골랐던 문자를 제외하고 골랐다.

하나의 문자를 고른 후에는 고른 문자를 s에 붙이고 remain에서는 제외한 후,

재귀호출을 해서 또 다음 문자열을 고르게 하였다.

remain이 빈문자열이 되면, 주어진 문자열을 모두 고르는데 성공했다는 얘기이므로 result에 추가해줬다.

 

result에는 같은 문자열이 포함되어있을 수 있는데

이는 sort한 후 unique를 해서 같은 문자열들은 제거해줬다.

 

sort를 한 이유는, unique가 인접한 문자열만을 제거해주기 때문이며

unique를 한 후 erase를 호출해준 이유는, unique가 실제로 같은 문자열을 제거해주는 것이 아니라

같은 문자열들을 맨 뒤로 보내버리기 때문에 unique 후에 실제로 result로부터 같은 문자열들을 제거해주기 위해서 erase를 호출해줘야한다.