문제 개요
이 문제에서는 크기가 m인 두 개의 배열 arr1[]과 arr2[], 그리고 하나의 값 N이 주어집니다. 우리의 과제는 두 배열의 합으로 구성된 집합에서 N번째 원소를 찾는 것입니다.
문제 설명 — 여기서 우리는 arr1의 원소 하나와 arr2의 원소 하나를 더한 값들로 집합을 만듭니다. 즉, sum = arr1[i] + arr2[j] (단, i, j < m) 형태의 모든 합을 모은 집합입니다. N이 주어지면 이 집합에서 N번째 원소의 값을 구해야 합니다.
예제로 문제 이해하기
입력
arr1[] = {3, 1, 5}, arr2[] = {6, 2, 8}, N = 4출력
7
설명
집합을 구성하는 원소들은 다음과 같습니다.
9 (3+6, 1+8), 5 (3+2), 11 (3+8, 5+6), 7 (1+6, 5+2), 3 (1+2), 13 (5+8)
오름차순으로 정렬하면: 3, 5, 7, 9, 11, 13
네 번째 원소는 7입니다.
해결 접근 방법
해결 방법은 단순합니다. 배열 원소들의 합을 모두 구하여 집합을 만드는 것입니다. 이를 위해 중첩 루프를 사용합니다.
- 바깥쪽 루프는 arr1의 원소를 순회합니다.
- 안쪽 루프는 arr2의 원소를 순회합니다.
- 안쪽 루프의 각 반복에서 두 원소의 합을 집합(std::set)에 저장합니다. std::set은 자동으로 정렬되며 중복 원소를 허용하지 않으므로, 별도의 정렬과 중복 제거 과정이 필요 없습니다.
모든 합이 집합에 저장되면, 집합을 순회하면서 N번째 원소를 찾아 반환합니다.
알고리즘 동작을 보여주는 프로그램
#include <iostream>
#include <set>
using namespace std;
int findNthElement(int arr1[], int arr2[], int m, int N) {
set<int> sumSet;
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
sumSet.insert(arr1[i] + arr2[j]);
}
}
int count = 0;
for (int element : sumSet) {
count++;
if (count == N)
return element;
}
return -1;
}
int main() {
int arr1[] = {3, 1, 5};
int arr2[] = {6, 2, 8};
int m = sizeof(arr1) / sizeof(arr1[0]);
int N = 4;
cout << "집합의 " << N << "번째 원소는 " << findNthElement(arr1, arr2, m, N) << "입니다.";
return 0;
}
출력
집합의 4번째 원소는 7입니다.
복잡도 분석
- 시간 복잡도: O(m² log m) — 중첩 루프로 m²개의 합을 계산하고, 각 합을 집합에 삽입하는 데 O(log m²)가 소요됩니다.
- 공간 복잡도: O(m²) — 집합에 최대 m²개의 원소가 저장될 수 있습니다.
마무리
이 접근 방식은 std::set의 정렬 및 중복 제거 특성을 활용하여 코드를 간결하게 유지합니다. 배열의 크기가 큰 경우에는 힙이나 이진 탐색 기반의 최적화 기법을 고려할 수 있지만, 문제의 요구 사항이 단순한 경우 위 방법이 가장 직관적이고 효율적인 구현 방법입니다.