[LeetCode] 1497. Check If Array Pairs Are Divisible by k

https://leetcode.com/problems/check-if-array-pairs-are-divisible-by-k/description/?envType=daily-question&envId=2024-10-01

leetcode - Check If Array Pairs Are Divisible by K

문제 유형 : 수학

문제 난이도 : Medium

 

문제

Given an array of integers arr of even length n and an integer k.

We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.

Return true If you can find a way to do that or false otherwise.

 

정수 배열이 n의 길이로 주어지고, 정수 k가 주어집니다.

n/2개의 쌍을 만들어서 두 수의 합이 모두 k에 의해 나눠지도록 하고 싶습니다.

방법이 있으면 true, 아니면 false를 반환하시오.

 

풀이

[0, k-1]까지의 범위의 배열을 만들어서, 각 배열의 요소들에 대해 모듈러 k를 한 연산결과의 카운트를 누적한다.

만약 나머지 0인 요소들이 홀수라면, false이다.

이외에도 1과 k-1, 2와 k-2, ...의 개수가 서로 맞지 않으면, false이다.

 

통과하면 true이다.

 

코드

C++

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        vector<int> count(k, 0);

        for (int num : arr) {
            int remainder = ((num % k) + k) % k;
            count[remainder]++;
        }

        if (count[0] % 2 != 0) {
            return false;
        }

        for (int i = 1; i < k; ++i) {
            if (count[i] != count[k - i]) {
                return false;
            }
        }

        return true;
    }
};