문제 소개
정수 n개로 이루어진 배열 arr가 주어졌을 때, arr[i]Carr[j] 값(조합)이 최대가 되도록 두 원소 arr[i]와 arr[j]를 찾아야 합니다. 만약 조건을 만족하는 쌍이 여러 개 존재한다면, 그중 아무거나 하나만 반환하면 됩니다.
예를 들어 입력 배열이 [4, 1, 2]라고 해보겠습니다. 4C1 = 4, 4C2 = 6, 2C1 = 2이므로 가능한 모든 쌍 중 (4, 2)가 가장 큰 조합 값을 가집니다. 따라서 출력은 "4 2"가 됩니다.
해결 접근 방식
조합 C(n, r)의 수학적 성질을 활용하면 문제를 효율적으로 풀 수 있습니다. C(n, r)은 n이 클수록 커지며, r이 n/2에 가까울수록 최대화됩니다. 이 성질을 바탕으로 다음과 같은 전략을 세울 수 있습니다.
- 배열을 오름차순으로 정렬합니다.
- 가장 큰 원소 v[n-1]을 N으로 선택합니다. n이 클수록 조합 값이 커지기 때문입니다.
- N/2에 가장 가까운 값을 가진 나머지 원소 하나를 R로 선택합니다.
N이 홀수인 경우에는 N/2가 정수로 떨어지지 않으므로, N//2와 N//2+1 두 지점을 모두 고려하여 어느 쪽에 더 가까운 원소가 있는지 비교해야 합니다.
알고리즘 단계
- 리스트 v를 정렬합니다.
- N := v[n-1]로 설정합니다.
- N이 홀수라면:
- first := N // 2, second := first + 1로 설정합니다.
- first 이하의 값 중 first와 가장 가까운 값(left)을 찾습니다.
- first보다 큰 첫 번째 값(right)을 찾습니다.
- (first - left)와 (right - second)를 비교하여 더 가까운 쪽을 결과로 출력합니다.
- N이 짝수라면:
- max := N // 2로 설정합니다.
- |v[i] - max|가 최소가 되는 원소 R을 찾습니다.
- N과 R을 함께 출력합니다.
구현 예제
다음 파이썬 코드를 통해 실제 동작을 확인해 보겠습니다.
def findMatrixPair(v, n):
v.sort()
N = v[n - 1]
if N % 2 == 1:
first = N // 2
second = first + 1
res1 = 3 * (10 ** 18)
left, right = -1, -1
temp = -1
for i in range(0, n):
if v[i] > first:
temp = i
break
else:
difference = first - v[i]
if difference < res1:
res1 = difference
left = v[i]
right = v[temp]
difference1 = first - left
difference2 = right - second
if difference1 < difference2:
print(N, left)
else:
print(N, right)
else:
max = N // 2
res = 3 * (10 ** 18)
R = -1
for i in range(0, n - 1):
difference = abs(v[i] - max)
if difference < res:
res = difference
R = v[i]
print(N, R)
v = [4, 1, 2]
n = len(v)
findMatrixPair(v, n)입력
[4, 1, 2], 3
출력
4 2
마무리
이 알고리즘은 정렬 후 한 번의 선형 탐색만 수행하므로 전체 시간 복잡도는 O(n log n)이며, 정렬 비용이 지배적입니다. 모든 쌍에 대해 nCr을 직접 계산하는 대신, 조합 값이 r = n/2 근처에서 최대가 된다는 성질만 활용하면 훨씬 적은 연산으로 정답을 구할 수 있다는 점이 이 풀이의 핵심입니다.