C#에서 문자열의 양쪽 절반이 동일한 문자 집합을 갖는지 확인하는 방법

이 글에서는 C#에서 주어진 문자열의 앞쪽 절반과 뒤쪽 절반이 동일한 문자 집합을 포함하고 있는지 확인하는 방법을 알아봅니다. 예를 들어 문자열 "timetime"은 앞쪽 절반 "time"과 뒤쪽 절반 "time"이 같은 문자들로 구성되어 있으므로 결과는 참(true)이 됩니다.

확인 절차

먼저 검사할 문자열을 설정합니다.

string s = "timetime";

그다음, 문자열의 두 절반에 등장한 각 알파벳 문자의 개수를 세기 위해 크기가 26인 정수 배열(카운터) 두 개를 준비합니다.

int []one = new int[MAX_CHAR];
int []two = new int[MAX_CHAR];

투 포인터(two-pointer) 기법을 활용합니다. 한 포인터는 문자열의 시작 부분에서, 다른 포인터는 끝 부분에서 출발해 서로를 향해 이동하면서 각 절반에 속한 문자의 빈도를 계산합니다.

for (int i = 0, j = l - 1; i < j; i++, j--) {
    one[str[i] - 'a']++;
    two[str[j] - 'a']++;
}

순회가 끝나면 두 배열을 비교하여 모든 문자의 빈도가 일치하는지 확인합니다. 단 하나라도 빈도가 다른 문자가 있다면 두 절반은 동일한 문자 집합이 아닌 것입니다. 참고로 문자열 길이가 홀수인 경우 가운데 문자는 어느 쪽 절반에도 속하지 않으므로 비교 대상에서 자연스럽게 제외됩니다.

전체 예제 코드

다음은 C#에서 문자열의 양쪽 절반이 동일한 문자 집합을 갖는지 확인하는 완전한 코드입니다.

using System;
class Demo {
    static int MAX_CHAR = 26;
    static bool findSameCharacters(string str) {
        int []one = new int[MAX_CHAR];
        int []two = new int[MAX_CHAR];
        int l = str.Length;
        if (l == 1)
        return true;
        for (int i = 0, j = l - 1; i < j; i++, j--) {
            one[str[i] - 'a']++;
            two[str[j] - 'a']++;
        }
        for (int i = 0; i < MAX_CHAR; i++)
        if (one[i] != two[i])
        return false;
        return true;
    }
    public static void Main() {
        string str = "timetime";
        if (findSameCharacters(str))
        Console.Write("Yes: Two halves are same!");
        else
        Console.Write("No! Two halves are not same!");
    }
}

실행 결과

Yes: Two halves are same!

동작 원리와 복잡도

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 또한 크기가 고정된 26칸짜리 배열 두 개만 사용하기 때문에 공간 복잡도는 O(1)로 매우 효율적입니다. 문자열 길이가 1인 경우에는 비교할 두 절반이 존재하지 않으므로 즉시 true를 반환하도록 처리했습니다.