C#으로 문자열 내 각 위치에서 특정 문자까지의 가장 긴 거리 구하는 방법

문자열과 특정 문자가 주어졌을 때, 문자열의 각 위치에서 해당 문자까지의 가장 긴 거리를 구하는 문제입니다. 이 문제는 양방향 탐색(Two-Pass) 기법을 사용하면 선형 시간 안에 효율적으로 해결할 수 있습니다.

접근 방법

핵심 아이디어는 두 개의 배열을 활용하는 것입니다.

• leftDis: 왼쪽에서 오른쪽으로 이동하며 각 위치에서 대상 문자까지의 거리를 저장합니다.
• rightDis: 오른쪽에서 왼쪽으로 이동하며 각 위치에서 대상 문자까지의 거리를 저장합니다.

탐색 중에 대상 문자를 만나면 해당 위치의 거리를 0으로 설정하고, 이후로는 카운트를 하나씩 증가시켜 나갑니다. 모든 탐색이 끝난 후 각 인덱스에서 두 배열 값 중 최댓값을 선택하면 가장 긴 거리를 구할 수 있습니다.

복잡도 분석

• 시간 복잡도 − O(n): 문자열을 두 번 순회하므로 선형 시간이 소요됩니다.
• 공간 복잡도 − O(n): 거리를 저장하기 위한 두 개의 배열이 필요합니다.

예제 코드

public class Arrays{
    public int[] LongestDistanceToCharacter(string s, char c){
        int stringLength = s.Length;
        int[] leftDis = new int[s.Length];
        int[] rightDis = new int[s.Length];
        leftDis = Enumerable.Range(0, s.Length).Select(n => int.MinValue).ToArray();
        rightDis = Enumerable.Range(0, s.Length).Select(n => int.MaxValue).ToArray();
        int count = int.MaxValue;
        for (int i = 0; i < rightDis.Length; i++){
            if (s[i] == c){
                count = 0;
                rightDis[i] = count;
            }
            else{
                if (count != int.MaxValue){
                    count++;
                    rightDis[i] = count;
                }
            }
        }
        count = int.MaxValue;
        for (int i = leftDis.Length - 1; i >= 0; i--){
            if (s[i] == c){
                count = 0;
                leftDis[i] = count;
            }
            else{
                if (count != int.MaxValue){
                    count++;
                    leftDis[i] = count;
                }
            }
        }
        int[] ans = new int[stringLength];
        for (int i = 0; i < stringLength - 1; i++){
            ans[i] = Math.Max(leftDis[i], rightDis[i]);
        }
        return ans;
    }
}

static void Main(string[] args){
    Arrays s = new Arrays();
    string ss = "lovecode";
    char c = 'e';
    var res = s.LongestDistanceToCharacter(ss, c);
    foreach (var item in res){
        Console.WriteLine(item);
    }
}

실행 결과

[2147483647,2147483647,2147483647,0,3,2,3,0]

입력 문자열 "lovecode"와 문자 'e'가 주어진 경우의 결과입니다. 문자 'e'가 등장하기 전의 위치들은 초기값인 int.MaxValue(2147483647)로 표시되며, 'e'가 있는 위치는 0, 나머지 위치는 가장 먼 'e'까지의 거리가 출력됩니다.