n개의 요소를 가진 배열 A와 m개의 요소를 가진 배열 B가 있다고 가정해 보겠습니다. 우리의 목표는 배열 A에서 한 요소 a를, 배열 B에서 한 요소 b를 선택하여 a + b의 값이 배열 A와 B 어느 쪽에도 존재하지 않도록 만드는 것입니다.
예를 들어 입력이 A = [3, 2, 2], B = [1, 5, 7, 7, 9]라고 한다면, 출력은 [3, 1]이 될 수 있습니다. 3 + 1 = 4는 어떤 배열에도 존재하지 않기 때문입니다. 물론 정답은 하나만 있는 것이 아니며, 3 + 9 = 12처럼 다른 조합 역시 유효한 답이 될 수 있습니다.
해결 접근 방식
이 문제는 의외로 간단한 방법으로 해결할 수 있습니다. 바로 각 배열에서 가장 큰 값을 선택하는 것인데, 그 이유는 다음과 같습니다.
- 배열 A의 최댓값을 a, 배열 B의 최댓값을 b라고 하면, a + b는 배열 A의 모든 요소보다 큽니다.
- 마찬가지로 a + b는 배열 B의 모든 요소보다도 큽니다.
- 따라서 a + b는 두 배열 어디에도 존재할 수 없습니다.
최댓값을 구하기 위해 다음 단계를 따릅니다.
배열 A를 오름차순으로 정렬 배열 B를 오름차순으로 정렬 A의 마지막 요소(최댓값)와 B의 마지막 요소(최댓값)를 반환
정렬을 사용하므로 전체 시간 복잡도는 O(n log n)입니다.
예제 코드
아래 C++ 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A, vector<int> B) {
sort(A.begin(), A.end());
sort(B.begin(), B.end());
cout << A[A.size() - 1] << ", " << B[B.size() - 1];
}
int main() {
vector<int> A = { 3, 2, 2 };
vector<int> B = { 1, 5, 7, 7, 9 };
solve(A, B);
}입력
{ 3, 2, 2 }, { 1, 5, 7, 7, 9 }출력
3, 9
배열 A의 최댓값 3과 배열 B의 최댓값 9를 더한 12는 두 배열 어디에도 존재하지 않으므로, 조건을 만족하는 올바른 답임을 확인할 수 있습니다.