문제 상황
두 사람이 함께 여행할 도시를 정하려고 합니다. 각자 선호하는 도시를 목록으로 작성했고, 우리는 두 사람 모두가 선택한 공통 도시를 찾아야 합니다.
이 연산은 집합의 교집합 성질과 매우 유사합니다. 두 목록을 각각 하나의 집합으로 간주한 뒤 교집합 연산을 수행하면 공통 요소를 쉽게 얻을 수 있습니다.
C++ STL의 set_intersection 활용하기
C++ 표준 템플릿 라이브러리(STL)에는 정렬된 두 범위의 교집합을 구하는 set_intersection 함수가 제공됩니다. 이 함수는 입력 범위가 반드시 오름차순으로 정렬되어 있어야 하므로, 호출 전에 sort로 두 목록을 정렬해야 한다는 점에 유의하세요.
예제 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> commonInterest(string set1[], int n1, string set2[], int n2) {
vector<string> v(min(n1, n2));
vector<string>::iterator it;
// 두 목록을 오름차순으로 정렬
sort(set1, set1 + n1);
sort(set2, set2 + n2);
// 정렬된 두 배열의 교집합 계산
it = set_intersection(set1, set1 + n1, set2, set2 + n2, v.begin());
v.resize(it - v.begin()); // 실제 교집합 크기만큼 잘라내기
return v;
}
int main() {
string first[] = { "Kolkata", "Hyderabad", "Chennai", "Delhi" };
int n1 = sizeof(first) / sizeof(first[0]);
string second[] = { "Mumbai", "Kolkata", "Durgapur", "Delhi" };
int n2 = sizeof(second) / sizeof(second[0]);
vector<string> v = commonInterest(first, n1, second, n2);
cout << "Common cities:";
for (int i = 0; i < v.size(); i++)
cout << ' ' << v[i];
cout << endl;
}
실행 결과
Common cities: Delhi Kolkata
두 목록에 공통으로 포함된 Delhi와 Kolkata가 정렬된 순서대로 출력됩니다. 교집합 결과의 실제 크기를 반환값으로 받아 v.resize()로 처리하면, 초기화되지 않은 빈 문자열이 함께 출력되는 문제도 예방할 수 있습니다.
최소 인덱스 합계가 가장 작은 공통 요소 찾기
공통 도시가 여러 개일 경우, 일반적으로 두 목록에서 인덱스 합계(첫 번째 목록 인덱스 + 두 번째 목록 인덱스)가 가장 작은 도시를 우선 선택합니다. 두 사람의 선호 순위를 모두 반영하는 방식이라고 할 수 있습니다. 이 경우 해시 맵(unordered_map)을 사용하면 정렬 없이도 O(n₁ + n₂) 시간 복잡도로 효율적으로 해결할 수 있습니다.
예제 코드
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <climits>
using namespace std;
vector<string> findCity(string list1[], int n1, string list2[], int n2) {
unordered_map<string, int> pos;
// 첫 번째 목록의 도시별 인덱스를 저장
for (int i = 0; i < n1; i++)
pos[list1[i]] = i;
vector<string> answer;
int minSum = INT_MAX;
// 두 번째 목록을 순회하며 최소 인덱스 합계 탐색
for (int j = 0; j < n2; j++) {
auto found = pos.find(list2[j]);
if (found != pos.end()) {
int sum = j + found->second;
if (sum < minSum) { // 더 작은 합계 발견
minSum = sum;
answer.clear();
answer.push_back(list2[j]);
} else if (sum == minSum) { // 합계가 같으면 모두 저장
answer.push_back(list2[j]);
}
}
}
return answer;
}
int main() {
string first[] = { "Kolkata", "Hyderabad", "Chennai", "Delhi" };
int n1 = sizeof(first) / sizeof(first[0]);
string second[] = { "Mumbai", "Kolkata", "Durgapur", "Delhi" };
int n2 = sizeof(second) / sizeof(second[0]);
vector<string> result = findCity(first, n1, second, n2);
cout << "Min index sum cities:";
for (const string& s : result)
cout << ' ' << s;
cout << endl;
}
실행 결과
Min index sum cities: Kolkata
Kolkata는 첫 번째 목록의 인덱스(0)와 두 번째 목록의 인덱스(1)를 더한 값이 1로 가장 작기 때문에 최종 선택됩니다. 반면 Delhi는 인덱스 합계가 3 + 3 = 6으로 더 크므로 제외됩니다.
정리
- 교집합 방식:
sort+set_intersection조합으로 구현하며, 시간 복잡도는 O(N log N)입니다. - 해시 맵 방식: 최소 인덱스 합계 조건까지 고려할 수 있으며, 시간 복잡도는 O(N)입니다.
단순히 공통 요소만 필요하다면 교집합 방식으로 충분하고, 두 목록 내 요소의 위치(선호 순위)가 중요한 문제라면 해시 맵 기반 접근이 더 적합합니다. 문제의 요구 사항에 따라 적절한 방법을 선택해 활용하시기 바랍니다.