stringsRearrangement

동일한 길이의 문자열로 이루어진 배열이 주어졌을 때, 연속하는 두 문자열 간에 정확히 한 문자만 차이 나도록 배열의 순서를 재배열할 수 있는지 여부를 판단하는 것입니다.

예를 들어, 문자열 배열이 ["abc", "xbc", "xxc"]라면, "abc"와 "xbc"는 한 문자만 다르며, "xbc"와 "xxc" 역시 한 문자만 다릅니다. 따라서 가능한 순서 재배열이므로 이 경우에는 true를 반환해야 합니다.

bool solution(string[] inputArray) {
   return Permute(inputArray, 0);
}
bool Permute(string[] arr, int start)
    {
        if (start == arr.Length)
        {
            // 순열이 완성된 경우, 인접한 두 문자열이 조건을 만족하는지 확인
            return CheckAdjacent(arr);
        }

        for (int i = start; i < arr.Length; i++)
        {
            // 현재 원소와 다른 원소들과 위치를 바꾸어가며 순열 생성
            Swap(ref arr[start], ref arr[i]);

            // 재귀 호출로 다음 위치의 원소 결정
            if (Permute(arr, start + 1))
                return true;

            // 원복
            Swap(ref arr[start], ref arr[i]);
        }

        return false;
    }
     bool CheckAdjacent(string[] arr)
    {
        // 인접한 두 문자열 사이에 정확히 하나의 문자만 다르도록 만들 수 있는지 확인
        for (int i = 0; i < arr.Length - 1; i++)
        {
            if (!DifferByOneChar(arr[i], arr[i + 1]))
                return false;
        }

        return true;
    }

   bool DifferByOneChar(string str1, string str2)
    {
        // 두 문자열 간에 정확히 하나의 문자만 다른지 확인
        int diffCount = str1.Zip(str2, (c1, c2) => c1 != c2 ? 1 : 0).Sum();
        return diffCount == 1;
    }

    void Swap<T>(ref T a, ref T b)
    {
        // 변수 교환을 위한 도우미 함수
        T temp = a;
        a = b;
        b = temp;
    }

Zip 함수는 두 문자열 간의 대응되는 문자 쌍을 생성하며, Sum 함수는 차이가 발생한 문자의 수를 계산합니다.

ref는 C#에서 사용되는 한 가지 키워드로, 메서드에 전달된 인수의 참조를 전달할 때 사용됩니다. 일반적으로 C#에서는 값 형식(구조체)을 인수로 전달할 때 메서드 내에서 변경된 내용이 호출자에 반영되지 않습니다. 하지만 ref 키워드를 사용하면 메서드 내에서 값 형식을 직접 참조로 전달할 수 있습니다.