파이썬으로 K보다 작은 두 수의 최대 합 구하기

문제 개요

정수 배열 A와 정수 K가 주어졌을 때, 다음 조건을 만족하는 최댓값 S를 찾는 문제입니다.

• 인덱스 i < j를 만족하는 두 원소 A[i]와 A[j]의 합이 S일 것
• S가 K보다 작을 것

만약 이러한 조건을 만족하는 두 원소가 존재하지 않는다면 -1을 반환해야 합니다.

예를 들어 A = [34, 23, 1, 24, 75, 33, 54, 8]이고 K = 60이라고 가정해 보겠습니다. 이 경우 출력값은 58입니다. 34와 24를 더하면 58이 되는데, 이 값은 60보다 작으면서 만들 수 있는 합 중 가장 크기 때문입니다.

풀이 접근 방법

가장 직관적인 방법은 모든 두 원소의 조합을 확인하는 브루트 포스(Brute Force) 방식입니다. 단계별로 살펴보면 다음과 같습니다.

1. 결과 변수 res를 -1로 초기화합니다.
2. 배열 A의 길이가 1이면 두 수의 합을 만들 수 없으므로 -1을 반환합니다.
3. i를 0부터 배열 길이까지 순회하면서, 각 i에 대해 j를 i+1부터 배열 길이까지 순회합니다.
4. temp = A[i] + A[j]를 계산한 뒤, temp가 K보다 작으면 res와 temp 중 더 큰 값을 res에 저장합니다.
5. 모든 반복이 끝나면 res를 반환합니다.

시간 복잡도

두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 크지 않다면 충분히 효율적이지만, 성능이 중요하다면 배열을 정렬한 후 투 포인터(Two Pointer) 기법을 활용해 O(n log n)으로 개선할 수 있습니다.

파이썬 구현 예제

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

class Solution(object):
    def twoSumLessThanK(self, A, K):
        ans = -1
        if len(A) == 1:
            return -1
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                temp = A[i] + A[j]
                if temp < K:
                    ans = max(ans, temp)
        return ans

ob1 = Solution()
print(ob1.twoSumLessThanK([34,23,1,24,75,33,54,8], 60))

입력

[34,23,1,24,75,33,54,8]
60

출력

58

정리

이 문제는 배열 내 서로 다른 위치에 있는 두 원소의 합 중에서 K 미만인 최댓값을 찾는 전형적인 탐색 문제입니다. 브루트 포스 방식은 구현이 간단하고 직관적이어서 문제 이해에 도움이 되며, 입력 크기가 커질 경우 정렬 기반 투 포인터 방식으로 최적화하는 것이 좋습니다.