LeetCode [628]: Maximum Product of Three Numbers

📌 LeetCode [628]: Maximum Product of Three Numbers

🔗 문제 링크

---

문제 설명 📄

정수 배열 nums가 주어졌을 때, 세 숫자의 곱 중 최대값을 반환하세요.

• 배열의 길이는 최소 3입니다.
• 음수와 양수 값이 포함될 수 있습니다.

---

문제 접근 방식 📋

1. 정렬을 활용:
   • 배열을 정렬하여 가장 큰 3개 값과 가장 작은 2개 값 및 가장 큰 값을 고려합니다.
   • 음수 두 개와 양수 하나를 곱했을 때가 더 클 수 있으므로 이를 함께 비교합니다.
2. 시간 복잡도: 정렬은 O(n \log n)입니다.
3. 공간 복잡도: 정렬된 배열을 재사용하므로 O(1)입니다.

---

Solution 💻

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()

        maxValue = float('-inf')
        maxValue = max(maxValue, nums[-1] * nums[-2] * nums[-3])
        maxValue = max(maxValue, nums[0] * nums[1] * nums[-1])

        return maxValue

시간 복잡도 ⏲️

• 정렬: O(n \log n)
• 최대값 계산: O(1)
• 총 시간 복잡도: O(n \log n)

공간 복잡도 🗄️

• 정렬된 배열 재사용: O(1)

---

리팩토링 🛠️

개선된 코드 (정렬 없이 O(n) 해결)

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        max1, max2, max3 = float('-inf'), float('-inf'), float('-inf')
        min1, min2 = float('inf'), float('inf')

        for num in nums:
            if num > max1:
                max1, max2, max3 = num, max1, max2
            elif num > max2:
                max2, max3 = num, max2
            elif num > max3:
                max3 = num

            if num < min1:
                min1, min2 = num, min1
            elif num < min2:
                min2 = num

        return max(max1 * max2 * max3, min1 * min2 * max1)

리팩토링 후 시간 복잡도 ⏲️

• 최대값, 최소값 계산: O(n)
• 총 시간 복잡도: O(n)

리팩토링 후 공간 복잡도 🗄️

• 추가 변수만 사용: O(1)

---