[LeetCode] 2966. Divide Array Into Arrays With Max Difference

https://leetcode.com/problems/divide-array-into-arrays-with-max-difference/description/?envType=daily-question&envId=2024-02-01

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Divide Array Into Arrays With Max Difference

문제 유형 : 정렬

문제 난이도 : Medium

 

문제

You are given an integer array nums of size n and a positive integer k.

Divide the array into one or more arrays of size 3 satisfying the following conditions:

• Each element of nums should be in exactly one array.
• The difference between any two elements in one array is less than or equal to k.

Return a 2D array containing all the arrays. If it is impossible to satisfy the conditions, return an empty array. And if there are multiple answers, return any of them.

 

당신은 n개의 정수를 배열로 받고, 정수 k를 받습니다.

배열의 요소를 각각 3개로 나눠서 아래 조건을 만족하도록 하시오.

각 요소는 정확히 한 배열에 들어가야 합니다.

배열 안에 두 요소의 차는 k이하여야 합니다

 

배열을 모두 포함하는 2차원배열을 반환하시오.

조건을 만족할 수 없으면, 빈 배열을 반환하시오.

여러 답안이 나올 수 있으나, 한 가지만 반환하면 됩니다.

 

풀이

배열을 정렬하면 쉽게 풀 수 있다.

for(int i = 0; i < n; i+=3) {}으로 반복문을 열고,

n이 3의 배수임이 보장이 되기 때문에, 부분 배열을 subarr(i, i+3) 로 만들면 된다.

이 부분배열에서 양 끝의값의 차가 k보다 크다면, 빈 배열을 반환하면 된다.

아니라면, 부분배열을 계속해서 2차원배열 안에 넣으면 정답이 된다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        const int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> answer;

        for(int i = 0; i < n; i+=3) {
            if(nums[i+2] - nums[i] > k) return {};

            vector<int> temp(nums.begin()+i, nums.begin()+i+3);
            answer.push_back(temp);
        }

        return answer;
    }
};