[리트코드] 1464. 배열의 두 요소의 최대 곱 (Python)

Maximum Product of Two Elements in an Array - LeetCode

문제

정수 배열이 주어지면 해당 배열의 두 가지 다른 인덱스를 선택후 그 곱의 최대값을 반환합니다.

 

과정

1. 가장 큰값과 두 번째로 큰값을 찾아 각 값에서 -1을 해준 후 곱한 결과를 리턴한다.
2. sorted를 이용하는 방법과 heapq를 이용하는 방법이 있다.

 

입력

[3,4,5,2]

출력

12

 

풀이

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = sorted(nums, reverse=True)
        return (n[0]-1)*(n[1]-1)

 

한 줄씩 코드 해석해보기

n = sorted(nums, reverse=True)

• 입력받은 배열을 큰 수부터 정렬한다.

return (n[0]-1)*(n[1]-1)

• 정렬된 배열에서 첫번째 값과 두번째 값에서 -1을 뺀 값을 곱한 후 리턴 해준다.

 

힙을 이용한 풀이

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        h = heapq.nlargest(2, nums)
        return (h[0] - 1) * (h[1] - 1)

• nlargest() : 가장 큰 값부터 순서대로 리스트에 넣어준다

 

sorted를 이용하는 방법은 시간 복잡도가 O(NlogN)이고, heapq는 O(logN)이기 때문에 힙이 더 빠르다.