Python으로 리스트에서 서로 다른 두 요소의 최대 곱 구하기

숫자로 이루어진 리스트 nums가 주어졌을 때, 서로 다른 두 요소를 곱했을 때 나올 수 있는 최댓값을 구하는 문제입니다.

예를 들어 입력이 nums = [8, -3, 1, -5]라면 출력은 15가 됩니다. 음수끼리 곱하면 양수가 되므로 (-3) × (-5) = 15가 이 경우의 최댓값입니다.

해결 접근 방법

핵심 아이디어는 간단합니다. 최대 곱은 다음 두 가지 경우 중 하나에서 나올 수 있습니다.

리스트에서 가장 큰 두 수의 곱
리스트에서 가장 작은 두 수(음수)의 곱 — 둘 다 음수라면 곱한 결과가 큰 양수가 될 수 있음

따라서 다음 단계로 문제를 해결할 수 있습니다.

n := 리스트 nums의 길이
nums_sort := 리스트 nums를 오름차순 정렬
max_left := 정렬된 리스트의 가장 작은 두 요소의 곱 (nums_sort[0] × nums_sort[1])
max_right := 정렬된 리스트의 가장 큰 두 요소의 곱 (nums_sort[n-1] × nums_sort[n-2])
ans := max_left와 max_right 중 더 큰 값
ans 반환

정렬에 O(n log n)의 시간이 걸리지만, 코드가 매우 직관적이고 구현이 간단하다는 장점이 있습니다.

구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

def solve(nums):
    nums_sort = sorted(nums)
    max_left = nums_sort[0] * nums_sort[1]
    max_right = nums_sort[-1] * nums_sort[-2]

    ans = max(max_left, max_right)
    return ans

nums = [8, -3, 1, -5]
print(solve(nums))

입력

[8, -3, 1, -5]

출력

복잡도 분석

시간 복잡도는 정렬 때문에 O(n log n)이며, 추가 공간은 정렬된 복사본 하나만 필요하므로 O(n)입니다.