[LeetCode - Biweekly Contest 90] 2453. Destroy Sequential Targets

2453. Destroy Sequential Targets

Medium

You are given a 0-indexed array nums consisting of positive integers, representing targets on a number line. You are also given an integer space.

You have a machine which can destroy targets. Seeding the machine with some nums[i] allows it to destroy all targets with values that can be represented as nums[i] + c * space, where c is any non-negative integer. You want to destroy the maximum number of targets in nums.

Return the minimum value of nums[i] you can seed the machine with to destroy the maximum number of targets.

 

Example 1:

Input: nums = [3,7,8,1,1,5], space = 2
Output: 1
Explanation: If we seed the machine with nums[3], then we destroy all targets equal to 1,3,5,7,9,... 
In this case, we would destroy 5 total targets (all except for nums[2]). 
It is impossible to destroy more than 5 targets, so we return nums[3].

Example 2:

Input: nums = [1,3,5,2,4,6], space = 2
Output: 1
Explanation: Seeding the machine with nums[0], or nums[3] destroys 3 targets. 
It is not possible to destroy more than 3 targets.
Since nums[0] is the minimal integer that can destroy 3 targets, we return 1.

Example 3:

Input: nums = [6,2,5], space = 100
Output: 2
Explanation: Whatever initial seed we select, we can only destroy 1 target. The minimal seed is nums[1].

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= space <= 109

---

문제 풀이

• 주어진 숫자 배열에서 space값의 배수를 더한 값이 몇개가 있는지 찾는 문제이다.
• 여기서 가장 많은 숫자를 가지고 있으면서 가장 작은 숫자를 찾아야한다.
• 예를 들어 [3, 7, 8, 1, 1, 5] 가 있고 space가 2라면 정답은 1이다.
• nums[i] + c * space이 식을 가지고 계산을 해보면 1은 1, 3, 5, 7이 가능하기 때문에 총 5개의 숫자가 있다. 
• 숫자 배열의 최대 길이가 10^5이기 때문에 O(NlogN)이하로 문제를 풀어야한다.
• 딕셔너리를 사용하여 각 숫자들의 나머지를 저장해야한다.
• nums[i] + c * space식을 보고 예시를 만들면, 1 + 2 * 2라고 해보자.
• 그럼 5가 되는데, 이 전체 값을 space로 나눠 나머지 값을 구하면 nums[i]값을 구할 수 있다.
  • [3, 7, 8, 1, 1, 5] 이고 space 2이면, 나머지들은 [1, 1, 0, 1, 1, 1]이 된다.
  • 여기서 나머지가 같은 1들의 숫자는 다섯개고 1이 될 수 있는 숫자의 최소값은 1이 된다.
• 쉽게 말해 나머지 + 몫 * 배수이다. 
• 모든 숫자들의 나머지의 개수를 모두 셈과 동시에 개수의 최대값을 저장한다.
• 그리고 for 루프를 한번더 사용하여 최대 개수를 가지고 있는 숫자의 최소값을 찾는다.

소스 코드

class Solution:
    def destroyTargets(self, nums: List[int], space: int) -> int:
        hash_table = defaultdict(int)
        max_val = -1 
        ans = 10 ** 9
        for num in nums:
            temp = num % space
            hash_table[temp] += 1
            max_val = max(max_val, hash_table[temp])
        for num in nums:
            temp = num % space
            if hash_table[temp] == max_val:
                ans = min(ans, num)
        return ans