C#으로 세 개의 정렬된 배열에서 공통 요소 찾기

개요

여러 개의 정렬된 배열이 있을 때, 모든 배열에 공통으로 존재하는 요소를 효율적으로 찾는 방법을 알아보겠습니다. 배열이 이미 정렬되어 있다는 특징을 활용하면 세 개의 인덱스(포인터)를 사용해 단 한 번의 순회만으로 공통 요소를 찾을 수 있습니다.

1. 세 개의 정렬된 배열 초기화

먼저 비교 대상이 될 세 개의 정렬된 배열을 초기화합니다.

int[] one = { 20, 35, 57, 70 };
int[] two = { 9, 35, 57, 70, 92 };
int[] three = { 25, 35, 55, 57, 67, 70 };

2. 알고리즘 동작 원리

세 개의 인덱스 변수 i, j, k를 사용해 각 배열을 동시에 순회하면서 다음과 같은 규칙으로 값을 비교합니다.

• 세 배열의 현재 값이 모두 같으면 공통 요소이므로 출력하고, 세 인덱스를 모두 증가시킵니다.
• 첫 번째 배열의 값이 두 번째 배열의 값보다 작으면 i를 증가시킵니다.
• 두 번째 배열의 값이 세 번째 배열의 값보다 작으면 j를 증가시킵니다.
• 그 외의 경우에는 k를 증가시킵니다.

while (i < one.Length && j < two.Length && k < three.Length) {
    if (one[i] == two[j] && two[j] == three[k]) {
        Console.Write(one[i] + " ");
        i++; j++; k++;
    }
    else if (one[i] < two[j])
        i++;
    else if (two[j] < three[k])
        j++;
    else
        k++;
}

이 방식은 값이 가장 작은 쪽의 인덱스를 계속 앞으로 이동시키며 세 배열의 값을 맞춰 나가는 원리입니다. 어떤 배열이라도 끝에 도달하면 루프가 종료됩니다.

전체 예제 코드

아래는 위 로직을 완성한 전체 C# 프로그램입니다.

using System;

class Demo {
    static void commonElements(int[] one, int[] two, int[] three) {
        int i = 0, j = 0, k = 0;
        while (i < one.Length && j < two.Length && k < three.Length) {
            if (one[i] == two[j] && two[j] == three[k]) {
                Console.Write(one[i] + " ");
                i++; j++; k++;
            }
            else if (one[i] < two[j])
                i++;
            else if (two[j] < three[k])
                j++;
            else
                k++;
        }
    }

    public static void Main() {
        int[] one = { 20, 35, 57, 70 };
        int[] two = { 9, 35, 57, 70, 92 };
        int[] three = { 25, 35, 55, 57, 67, 70 };

        Console.Write("공통 요소: ");
        commonElements(one, two, three);
    }
}

실행 결과

공통 요소: 35 57 70

정리

이 알고리즘은 각 배열을 한 번씩만 순회하므로 시간 복잡도는 O(n1 + n2 + n3)로 매우 효율적입니다. 만약 배열이 정렬되어 있지 않다면, 먼저 Array.Sort() 등으로 정렬한 후 이 방법을 적용하는 것이 좋습니다.