[LeetCode] 2529. Maximum Count of Positive Integer and Negative Integer (Python)

 

난이도: Easy

Problem Description

---

 

Given an array nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.

• In other words, if the number of positive integers in nums is pos and the number of negative integers is neg, then return the maximum of pos and neg.

Note that 0 is neither positive nor negative.

 

Problem Example

---

Example 1:

Input: nums = [-2,-1,-1,1,2,3]
Output: 3
Explanation: There are 3 positive integers and 3 negative integers. The maximum count among them is 3.

Example 2:

Input: nums = [-3,-2,-1,0,0,1,2]
Output: 3
Explanation: There are 2 positive integers and 3 negative integers. The maximum count among them is 3.

Example 3:

Input: nums = [5,20,66,1314]
Output: 4
Explanation: There are 4 positive integers and 0 negative integers. The maximum count among them is 4.

 

Constraints

---

• 1 <= nums.length <= 2000
• -2000 <= nums[i] <= 2000
• nums is sorted in a non-decreasing order.

 

Follow up: Can you solve the problem in O(log(n)) time complexity?

 

 

✏️ Solution

---

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        return max(len(nums) - bisect_left(nums, 1), bisect_right(nums,-1))

 

단순히 생각하여 nums의 모든 요소를 탐색하여 positive integer와 negative integer를 다 세고 최대 값을 찾을 수 있지만, 문제에서 O(log(n))의 시간복잡도로 풀어볼 수 있냐고 제안했기 때문에 이진탐색을 이용하여 문제를 해결했다.

 

이진탐색을 통해 왼쪽을 기준으로하여 1이 들어갈 수 있는 위치와 오른쪽을 기준으로하여 -1이 들어갈 수 있는 위치를 찾으면 된다.

 

예를 들어 nums가 [-2, -1, -1, 1, 2, 3]이라고 할 때, 1이 들어갈 수 있는 위치는 3이다. 따라서 총 nums의 갯수와 1이 들어갈 수 있는 위치의 수를 빼면 positive integer의 수를 쉽게 구할 수 있다. 6 - 3 = 3

 

또한 -1이 오른쪽을 기준으로 했을 때 들어갈 수 있는 위치는 3이다. 따라서 negative integer의 수는 3이된다.

 

이는 nums가 정렬되어 있기 때문에 이진탐색을 통해 구할 수 있다.

 

bisect함수들을 한번 써볼 수 있는 좋은 문제였던 것 같다.

 

 

⚙️ Runtime & Memory

---

 

 

---

문제: 2529. Maximum Count of Positive Integer and Negative Integer

 

깃허브: github

algorithmPractice/LeetCode/2614-maximum-count-of-positive-integer-and-negative-integer at main · laewonJeong/algorithmPractice