Python으로 세 개의 정렬된 배열에서 공통 요소 찾는 방법

이 글에서는 먼저 사용자 입력으로 받은 정렬되지 않은 세 개의 배열을 생성한 뒤, 세 배열을 모두 오름차순으로 정렬합니다. 각 배열의 크기는 n1, n2, n3이며, 모든 배열의 시작 인덱스는 0입니다. 즉, i=0, j=0, k=0으로 초기화한 후 세 배열의 요소를 하나씩 순회하면서 세 배열의 현재 값이 서로 같은지 확인합니다. 세 값이 모두 같으면 해당 요소를 출력하고, 그렇지 않으면 비교 결과에 따라 포인터를 앞으로 이동시켜 탐색을 계속합니다.

예제

A = {1, 2, 3, 4, 5}
B = {2, 5, 12, 22, 7}
C = {1, 9, 2, 89, 80}

출력

알고리즘

commonele(A1, A2, A3, n1, n2, n3)
/* A1, A2, A3는 정렬된 세 개의 정수 배열이며, size1, size2, size3는 각 배열의 크기입니다. */
Step 1: A1, A2, A3의 시작 인덱스를 초기화합니다.
   i = 0, j = 0, k = 0
Step 2: 세 배열이 모두 끝나지 않은 동안 반복 순회합니다.
   while (i < size1 && j < size2 && k < size3)
Step 3: A1[i], A2[j], A3[k]의 값을 비교합니다. 세 값이 모두 같으면 해당 요소를 출력하고 세 포인터를 모두 증가시키며, 그렇지 않으면 가장 작은 값을 가진 배열의 포인터만 앞으로 이동시킵니다.
Step 4: while 루프 종료

예제 코드

# 세 개의 정렬된 배열에서 공통 요소를 출력하는 프로그램
def commonele(X, Y, Z, n1, n2, n3):
   i, j, k = 0, 0, 0
   print("공통 요소 ::>")
   while (i < n1 and j < n2 and k < n3):
      if (X[i] == Y[j] and Y[j] == Z[k]):
         print(X[i])
         i += 1
         j += 1
         k += 1
      elif X[i] < Y[j]:
         i += 1
      elif Y[j] < Z[k]:
         j += 1
      else:
         k += 1

# 메인 프로그램
A = list()
B = list()
C = list()
n1 = int(input("첫 번째 리스트의 크기를 입력하세요 ::"))
n2 = int(input("두 번째 리스트의 크기를 입력하세요 ::"))
n3 = int(input("세 번째 리스트의 크기를 입력하세요 ::"))
print("첫 번째 리스트의 요소를 입력하세요 ::")
for i in range(int(n1)):
   k = int(input(""))
   A.append(k)
print("두 번째 리스트의 요소를 입력하세요 ::")
for j in range(int(n2)):
   k1 = int(input(""))
   B.append(k1)
print("세 번째 리스트의 요소를 입력하세요 ::")
for j in range(int(n3)):
   k1 = int(input(""))
   C.append(k1)
X = sorted(A)
Y = sorted(B)
Z = sorted(C)
print("정렬된 첫 번째 리스트 ::>", X)
print("정렬된 두 번째 리스트 ::>", Y)
print("정렬된 세 번째 리스트 ::>", Z)
commonele(X, Y, Z, n1, n2, n3)

실행 결과

첫 번째 리스트의 크기를 입력하세요 :: 4
두 번째 리스트의 크기를 입력하세요 :: 4
세 번째 리스트의 크기를 입력하세요 :: 5
첫 번째 리스트의 요소를 입력하세요 ::
23
12
45
8
두 번째 리스트의 요소를 입력하세요 ::
34
8
45
120
세 번째 리스트의 요소를 입력하세요 ::
2
4
8
45
1
정렬된 첫 번째 리스트 ::> [8, 12, 23, 45]
정렬된 두 번째 리스트 ::> [8, 34, 45, 120]
정렬된 세 번째 리스트 ::> [1, 2, 4, 8, 45]
공통 요소 ::>
8
45

코드 설명

이 알고리즘은 세 배열이 이미 정렬되어 있다는 특성을 활용합니다. 세 개의 포인터(i, j, k)가 각각 X, Y, Z 배열의 현재 위치를 가리키며, 아래 규칙에 따라 진행됩니다.

X[i] == Y[j] == Z[k] : 세 값이 모두 같으므로 공통 요소입니다. 출력한 뒤 세 포인터를 모두 한 칸씩 이동합니다.
X[i] < Y[j] : X[i]는 공통 요소가 될 수 없으므로 i를 증가시킵니다.
Y[j] < Z[k] : Y[j]는 공통 요소가 될 수 없으므로 j를 증가시킵니다.
그 외의 경우 : Z[k]가 가장 작은 값이므로 k를 증가시킵니다.

어느 한 배열이라도 끝에 도달하면 더 이상 세 배열에 공통으로 존재하는 요소가 없으므로 반복이 종료됩니다. 이 방식은 세 배열을 각각 한 번씩만 순회하므로 시간 복잡도가 O(n1 + n2 + n3)로 매우 효율적이며, 집합(set) 같은 추가 자료구조 없이도 교집합을 구할 수 있다는 장점이 있습니다.