[LeetCode/Easy] 2644. Find the Maximum Divisibility Score

1. Input

1) int[] nums

2) int[] divisors

 

2. Output

1) nums의 요소들 중 divisors[i]로 나누어 떨어지는 요소의 수를 divisibility score라고 할 때, 가장 큰 점수의 divisors[i]를 반환

- 가장 큰 점수가 여러개 나오는 경우, 가장 작은 divisors[i]를 반환

 

3. Constraint

1) 1 <= nums.length, divisors.length <= 1000

2) 1 <= nums[i], divisors[i] <= 10^9

 

4. Example

Input: nums = [4,7,9,3,9], divisors = [5,2,3] -> Output: 3

설명:

- 5로 나누어 떨어지는 숫자는 없다.

- 2로 나누어 떨어지는 숫자는 4 1개이다.

- 3으로 나누어 떨어지는 숫자는 9,3,9의 3개이다.

- 따라서 개수가 가장 많은 3을 반환한다.

 

5. Code

1) 첫 코드(2023/05/08)

class Solution {
    public int maxDivScore(int[] nums, int[] divisors) {
        Arrays.sort(divisors);
        int min = 0, score = 0;
        for(int i=divisors.length-1 ; i>=0 ; i--){
            int count = 0;
            for(int j=0 ; j<nums.length ; j++)
                count += nums[j]%divisors[i]==0 ? 1 : 0;
            if(count>=score){
                score = count;
                min = divisors[i];
            }
        }
        return min;
    }
}

2) 다시 풀어본 코드(2023/05/08)

class Solution {
    public int maxDivScore(int[] nums, int[] divisors) {
        HashMap<Integer,Integer> m = new HashMap<>();
        int max = 0;
        for(int i=divisors.length-1 ; i>=0 ; i--){
            int count = 0;
            for(int j=0 ; j<nums.length ; j++)
                count += nums[j]%divisors[i]==0 ? 1 : 0;
            if(count>=max){
                max = count;
                m.put(divisors[i], max);
            }
        }
        Iterator it = m.entrySet().iterator();
        ArrayList<Integer> list = new ArrayList<>();
        while(it.hasNext()){
            Map.Entry e = (Map.Entry)it.next();
            if((int)e.getValue()==max)
                list.add((int)e.getKey());
        }
        list.sort(Comparator.naturalOrder());
        return list.get(0);
    }
}

- 메모리는 조금 더 먹고, 속도는 조금 더 빨랐다. 하지만 그래도 둘다 영..