숫자로 이루어진 리스트가 주어졌을 때, 서로 다른 두 요소의 곱 중 가장 큰 값을 찾아야 하는 경우가 자주 있습니다. 예를 들어 입력 리스트가 [5, 3, 7, 4]라면, 가장 큰 곱은 7 × 5 = 35가 됩니다.
문제 해결 접근 방식
이 문제는 브루트 포스(Brute Force) 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 최댓값을 저장할 변수
curr_max를 음의 무한대(-inf)로 초기화합니다. - 이중 반복문을 사용하여 리스트 내 모든 서로 다른 두 요소의 조합(i, j)을 확인합니다.
- 두 요소의 곱이 현재
curr_max보다 크면 값을 갱신합니다. - 모든 조합을 확인한 후
curr_max를 반환합니다.
구현 예제 코드
아래 코드를 통해 실제 동작 과정을 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, nums):
curr_max = float('-inf')
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] * nums[j] > curr_max:
curr_max = nums[i] * nums[j]
return curr_max
ob = Solution()
print(ob.solve([5, 3, 7, 4]))
입력
[5, 3, 7, 4]
출력
35
시간 복잡도 및 개선 방법
위 방법은 이중 반복문을 사용하기 때문에 시간 복잡도는 O(n²)입니다. 리스트의 크기가 커지면 성능이 저하될 수 있습니다.
더 효율적으로 해결하려면 리스트를 정렬하는 방법을 활용할 수 있습니다. 정렬 후에는 최대 곱이 다음 두 경우 중 하나에 해당합니다.
- 가장 큰 두 양수의 곱:
nums[-1] * nums[-2] - 가장 작은 두 음수의 곱(음수 × 음수 = 양수):
nums[0] * nums[1]
정렬 기반 접근법의 코드는 다음과 같습니다.
class Solution:
def solve(self, nums):
nums.sort()
return max(nums[0] * nums[1], nums[-1] * nums[-2])
이 방법의 시간 복잡도는 정렬에 의해 O(n log n)으로, 브루트 포스 방식보다 효율적입니다. 음수가 포함된 리스트에서도 정확한 결과를 보장한다는 장점이 있습니다.