세 개의 정수 배열 arr1, arr2, arr3이 중복 없이 엄격하게 증가하는 순서로 정렬되어 있다고 가정해 봅시다. 이때 세 배열 모두에 등장하는 정수만 골라 정렬된 배열 형태로 반환해야 합니다. 예를 들어 배열이 [1,2,3,4,5], [1,2,5,7,9], [1,3,4,5,8]이라면 세 배열에 공통으로 존재하는 값은 1과 5이므로 출력은 [1,5]가 됩니다.
접근 방법 1: 해시 맵(빈도 카운팅) 활용
각 배열의 원소 등장 여부를 해시 맵에 기록한 뒤, 값의 범위를 순회하면서 세 맵에 모두 존재하는 값을 결과 배열에 추가하는 방식입니다. 문제 조건상 원소 값이 1 이상 2000 이하라고 가정할 수 있으므로 이 범위만 확인하면 됩니다.
- 결과를 담을 배열 res를 정의합니다.
- 세 개의 맵 f1, f2, f3를 생성합니다.
- i를 0부터 arr1의 길이까지 반복하며 f1[arr1[i]]를 1씩 증가시킵니다.
- 같은 방식으로 arr2와 arr3의 원소도 각각 f2, f3에 기록합니다.
- i를 1부터 2000까지 순회하면서 f1[i], f2[i], f3[i]가 모두 참이면 i를 res에 삽입합니다.
- res를 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i < v.size(); i++){
cout << v[i] << ", ";
}
cout << "]" << endl;
}
class Solution {
public:
vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
vector<int> ans;
unordered_map<int,int> f1, f2, f3;
for(int i = 0; i < arr1.size(); i++){
f1[arr1[i]]++;
}
for(int i = 0; i < arr2.size(); i++){
f2[arr2[i]]++;
}
for(int i = 0; i < arr3.size(); i++){
f3[arr3[i]]++;
}
for(int i = 1; i <= 2000; i++){
if(f1[i] && f2[i] && f3[i]) ans.push_back(i);
}
return ans;
}
};
main(){
Solution ob;
vector<int> v1 = {1,2,3,4,5};
vector<int> v2 = {1,2,5,7,9};
vector<int> v3 = {1,3,4,5,8};
print_vector(ob.arraysIntersection(v1, v2, v3));
}
입력
[1,2,3,4,5] [1,2,5,7,9] [1,3,4,5,8]
출력
[1,5]
접근 방법 2: 세 포인터 기법 (더 효율적인 방법)
배열이 이미 정렬되어 있다는 점을 활용하면 해시 맵 없이도 문제를 해결할 수 있습니다. 세 배열마다 포인터를 하나씩 두고 값을 비교하며 앞으로 이동하는 방식으로, 추가 메모리를 거의 사용하지 않는다는 장점이 있습니다.
- 포인터 i, j, k를 각각 0으로 초기화합니다.
- 세 포인터가 모두 배열 범위 안에 있는 동안 반복합니다.
- arr1[i] == arr2[j] == arr3[k]이면 공통 원소이므로 결과에 추가하고 세 포인터를 모두 전진시킵니다.
- 그렇지 않다면 세 값 중 가장 작은 값을 가진 포인터만 한 칸 전진시킵니다. 작은 값은 다른 배열에서 공통값이 될 수 없기 때문입니다.
예제 코드
class Solution {
public:
vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
vector<int> ans;
int i = 0, j = 0, k = 0;
while(i < arr1.size() && j < arr2.size() && k < arr3.size()){
if(arr1[i] == arr2[j] && arr2[j] == arr3[k]){
ans.push_back(arr1[i]);
i++; j++; k++;
} else if(arr1[i] <= arr2[j] && arr1[i] <= arr3[k]){
i++;
} else if(arr2[j] <= arr1[i] && arr2[j] <= arr3[k]){
j++;
} else {
k++;
}
}
return ans;
}
};
복잡도 분석
- 해시 맵 방식: 시간 복잡도는 O(n1 + n2 + n3 + R)이며(R은 값의 최대 범위인 2000), 세 개의 맵을 저장해야 하므로 O(n)의 추가 공간이 필요합니다.
- 세 포인터 방식: 시간 복잡도는 O(n1 + n2 + n3)이고, 결과 배열을 제외하면 추가 공간이 거의 없어 O(1)입니다. 입력이 정렬되어 있는 경우에는 이 방법이 가장 효율적입니다.