문제 소개
알고리즘 문제에서 자주 만나게 되는 상황 중 하나는 두 개의 정렬된 배열이 주어졌을 때, 두 배열에 공통으로 존재하지 않는 요소(고유 요소)만 골라서 출력하는 것입니다.
예를 들어 다음과 같은 입력이 주어진다고 가정해 보겠습니다.
입력 : array1[] = {1, 4, 6, 9, 12}
array2[] = {2, 4, 7, 8, 9, 10}
출력 : 1 2 6 7 8 10 12위 예시에서 4와 9는 두 배열 모두에 존재하는 공통 요소이므로 제외되고, 나머지 값들이 오름차순으로 출력됩니다.
해결 아이디어: 투 포인터(Two Pointer) 기법
두 배열이 이미 정렬되어 있기 때문에, 각 배열의 시작 위치에 하나씩 포인터(i, j)를 두고 앞에서부터 비교해 나가면 한 번의 순회만으로 답을 구할 수 있습니다.
array1[i] < array2[j]→ 해당 값은 array2에는 없으므로 출력하고i를 증가array1[i] > array2[j]→ 해당 값은 array1에는 없으므로 출력하고j를 증가array1[i] == array2[j]→ 공통 요소이므로 출력하지 않고i와j를 모두 증가
한쪽 배열의 순회가 끝나면, 남은 배열의 요소 중 상대 배열의 현재 값과 같지 않은 것만 이어서 출력하면 됩니다.
알고리즘 단계
START
Step 1 -> int형 요소를 가진 두 배열 array1, array2와 변수 n1, n2, i=0, j=0 선언
Step 2 -> sizeof(array1)/sizeof(array1[0]) 으로 array1의 요소 개수 계산
Step 3 -> sizeof(array2)/sizeof(array2[0]) 으로 array2의 요소 개수 계산
Step 4 -> i<n1 이고 j<n2 인 동안 반복
IF array1[i] < array2[j]
array1[i++] 출력
ELSE IF array1[i] > array2[j]
array2[j++] 출력
ELSE
i++ 와 j++ (공통 요소는 건너뜀)
Step 5 -> 반복 종료
Step 6 -> i < n1 이고 array1[i] != array2[j] 인 동안
남은 array1 요소 출력
Step 7 -> j < n2 이고 array2[j] != array1[i] 인 동안
남은 array2 요소 출력
STOP
C 언어 구현 예제
#include <stdio.h>
int main(int argc, char const *argv[]) {
int array1[] = {1, 4, 6, 9, 12};
int array2[] = {2, 4, 7, 8, 9, 10};
int n1, n2, i = 0, j = 0;
// 각 배열의 요소 개수 계산
n1 = sizeof(array1) / sizeof(array1[0]);
n2 = sizeof(array2) / sizeof(array2[0]);
// 두 배열을 동시에 순회하며 비교
while (i < n1 && j < n2) {
if (array1[i] < array2[j]) // array1의 값이 더 작으면 고유 요소
printf("%d\n", array1[i++]);
else if (array1[i] > array2[j]) // array2의 값이 더 작으면 고유 요소
printf("%d\n", array2[j++]);
else { // 값이 같으면 공통 요소이므로 건너뜀
i++;
j++;
}
}
// array1에 남은 요소 출력
while (i < n1 && array1[i] != array2[j])
printf("%d\n", array1[i++]);
// array2에 남은 요소 출력
while (j < n2 && array2[j] != array1[i])
printf("%d\n", array2[j++]);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
1
2
6
7
8
10
12
복잡도 분석
- 시간 복잡도: O(n1 + n2) — 두 배열을 각각 한 번씩만 순회합니다.
- 공간 복잡도: O(1) — 추가적인 배열이나 자료구조 없이 포인터 변수만 사용합니다.
정렬된 배열이라는 전제 조건 덕분에 해시셋 같은 별도의 자료구조 없이도 효율적으로 고유 요소를 찾아낼 수 있습니다. 만약 배열이 정렬되어 있지 않다면, 먼저 정렬(O(n log n))을 수행한 뒤 위 알고리즘을 적용하면 됩니다.