[Leetcode] 1464. Maximum Product of Two Elements in an Array

✅ 문제 - 가장 큰 두 수 곱하기

 

 

 

 

주어진 리스트에서 가장 큰 수 2개를 뽑아 -1씩 해주고 곱해주는 문제다.

 

---

 

✅ 나의 풀이

처음에는 리스트를 이용한 풀이법을 생각해 보았다. 하지만 이렇게 될 경우 리스트 전체를 순회해야 해서 최악의 경우 시간복잡도가 올라갈 것이라고 생각했다. 최댓값을 이용해서 간단하게 풀 수 있는 문제라 직전에 배운 힙을 이용해서 풀어봤다.

💡 힙이란? 데이터에서 최대값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리

 

 

1) 힙 이용 - 런타임 42ms 메모리 17.4MB

import heapq
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        
        # 최소힙으로 변환되는 것이 기본이므로 최대힙으로 heapify를 해야함
        # nums의 요소를 음수로 저장하면 최소힙과 반대로 저장되므로 최대힙이 됨

        nums = [-num for num in nums]
        heapq.heapify(nums)
        
        num1 = -heapq.heappop(nums)
        num2 = -heapq.heappop(nums)
        
        return (num1-1)*(num2-1)

 

 

파이썬에 내장된 heapq 모듈을 이용해서 풀었다.

 

파이썬에서 heapify를 통해 리스트에서 힙으로의 변환이 가능한데, 이 경우는 최소힙으로만 변환이 가능하다.

따라서 -를 붙여 힙 변환을 하게 되면 반대로 힙 정렬이 되어 내가 필요한 최댓값이 최소값으로 가게 된다.

이렇게 하는 이유는 heappop 연산은 heap에서 가장 작은 원소를 뽑아내기 때문에 결론적으로 내가 필요한 최대값 요소를 뽑아낼 수 있기 때문이다.

 

예를 들어, 

nums = [3,4,5,2] 일 때, 바로 heapify를 하면 [2, 3, 5, 4]로 최소힙이 된다.

nums = [-3, -4, -5, -2] 일 때는 힙 정렬 후 [-5, -4, -3, -2]가 된다.

 

max값을 구하기 위해서는 5와 4가 필요한데 pop연산 시 최솟값인 2부터 제거되기 때문에

음수를 만들어주고 난 후에 -5, -4를 뽑아내 양수로 바꿔주면 되는 것이다.

 

---

 

2) 정렬 이용