C#으로 문자열의 각 위치에서 특정 문자까지의 최단 거리 구하기

문자열 s와 문자 c가 주어졌을 때, 문자열의 각 인덱스에서 가장 가까운 문자 c까지의 거리를 담은 배열을 반환하는 문제입니다. 이 문제는 양방향 탐색(Two-Pass) 기법을 사용하면 선형 시간 안에 효율적으로 해결할 수 있습니다.

접근 방식

핵심 아이디어는 다음과 같습니다.

먼저 leftDis와 rightDis라는 두 개의 배열을 생성합니다. leftDis는 왼쪽에서 오른쪽 방향으로 이동하며 계산한 거리를 저장하고, rightDis는 오른쪽에서 왼쪽 방향으로 이동하며 계산한 최단 거리를 저장합니다. 탐색 중에 목표 문자 c를 만나면 해당 위치의 거리를 0으로 기록하고, 이후에는 카운트를 하나씩 증가시켜 나갑니다. 모든 탐색이 끝난 후 마지막 단계에서 두 배열의 같은 인덱스 값 중 더 작은 값을 선택하면, 각 위치에서 문자 c까지의 최단 거리를 얻을 수 있습니다.

• 시간 복잡도: O(n) — 문자열을 앞뒤로 각각 한 번씩 순회합니다.
• 공간 복잡도: O(n) — 거리를 저장하기 위한 배열 두 개가 필요합니다.

C# 구현 예제

public class Arrays{
    public int[] ShortestDistanceToCharacter(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;
        // 오른쪽 방향 탐색: 각 위치에서 왼쪽에 있는 가장 가까운 'c'까지의 거리
        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;
        // 왼쪽 방향 탐색: 각 위치에서 오른쪽에 있는 가장 가까운 'c'까지의 거리
        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; i++){
            ans[i] = Math.Min(leftDis[i], rightDis[i]);
        }
        return ans;
    }
}

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

실행 결과

[3, 2, 1, 0, 1, 2, 1, 0]

동작 원리 살펴보기

예제 입력 "lovecode"에서 문자 'e'는 인덱스 3과 7에 위치합니다. 각 인덱스별 최단 거리는 다음과 같이 계산됩니다.

이처럼 왼쪽 탐색과 오른쪽 탐색의 결과를 비교하여 더 작은 값을 취하면, 문자열 전체에 대해 각 위치에서 목표 문자까지의 최단 거리를 정확하게 구할 수 있습니다.