Aracade Intro #33 stringsRearrangement. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제, example, c++ java c# scalar
Q.
Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at consecutive positions would differ by exactly one character.
주어진 같은 길이의 string 배열들에서, 한개의 char 씩만 교체 가능해서 연속적으로 이어지는 자리로 재배치가 가능한지 확인해봐라.
어려워서 오래 걸렸던 것으로 기억하는데 하도 오래되서 봐도 어떻게 풀었었는지 가물가물함
e.g.
Input -> InputArray = ["aba", "bbb", "bab"]
Output -> stringsRearrangement(inputArray) = false
All rearrangements don't satisfy the description condition.
Input -> InputArray = ["ab", "bb", "aa"]
Output -> stringsRearrangement(inputArray) = true
Strings can be rearranged in the following way: "aa", "ab", "bb".
* 한번에 한글자씩 바꿔서 전체 배열의 string 들이 연결될 수 있다.
* It can be connected changing only one character each move.
전체 스트링 배열 중 재배열해서 순서대로 딱 한글자씩만 다르게 재배열 가능한지 아닌지
Permutation 써서 다시 풀어볼 필요있음 // 그래도 재귀를 좀 더 깨끗하게 쪼개서 푸는게 나은듯
// Process
// 1. Input string vector
// 2. iterate from begin to end (i)
// 2.1. call recursive function
// 2.1.1. if it's true - answer is true
// 2.1.2. if it's false - pass to next
// 3. return answer
//
// 1. Input string vector with front string
// 2. iterate from begin to end (i) (answer == false
// && [i] has only one diffecent char with front string)
// 2.1. iterate from begin to end (j) (answer == false)
// 2.1.1. check if it's different just one char
// 2.1.1.1. if it's true - call recuresive function
// 2.1.1.2. false - pass to next
//
// One more array for saving previous ordered values needed.
// It's possible to make another function for recursive. didn't know that (permutation)
//처리과정
//1.
Code.. Lemme see code..
코드.. 코드를 보자...
bool stringsRearrangement(std::vector<std::string> inputArray) {
bool answer = false;
if (inputArray.size() == 1)
{
answer = true;
}
std::vector<std::string> vectorBuffer(inputArray);
for (int i = 0; i < inputArray.size() && answer == false; ++i)
{
inputArray.erase(inputArray.begin() + i);
answer = recursiveStringsRearrangement(inputArray, vectorBuffer[i]);
if (answer == false)
{
inputArray = vectorBuffer;
}
}
return answer;
}
bool recursiveStringsRearrangement(std::vector<string> inputArray, string frontString) {
bool answer = false;
for (int i = 0; i < inputArray.size() && answer == false; ++i)
{
bool isConnected = onlyOneCharDiffer(inputArray[i], frontString);
if (isConnected == true)
{
if (inputArray.size() == 1)
{
answer = true;
}
std::vector<std::string> vectorBuffer(inputArray);
for (int j = 0; j < inputArray.size() && answer == false; ++j)
{
if (i != j)
{
bool oneCharDiffer = onlyOneCharDiffer(inputArray[i], inputArray[j]);
if (oneCharDiffer == true)
{
string tempBuffer = inputArray[j];
inputArray.erase(inputArray.begin() + i);
inputArray.insert(inputArray.begin(), tempBuffer);
if (i > j)
{
inputArray.erase(inputArray.begin() + j+1);
}
else
{
inputArray.erase(inputArray.begin() + j);
}
answer = recursiveStringsRearrangement(inputArray, vectorBuffer[i]);
if (answer == false)
{
inputArray = vectorBuffer;
}
}
}
}
}
}
return answer;
}
bool onlyOneCharDiffer(string string1, string string2) {
bool answer = false;
int count = 0;
for (i = 0; i < string1.size() && count < 2; ++i)
{
if (string1[i] != string2[i])
{
++count;
}
}
if (count == 1)
{
answer = true;
}
return answer;
}
Something you might like....
2018/12/03 - [Life/Health care] - Lecithin 레시틴 usage/side effects/dosage 효능/부작용/용법
2018/12/02 - [Life/Health care] - Maca 마카 usage/side effects/dosage 효능/부작용/용법
2018/11/29 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법