본문으로 건너뛰기

2966 - Divide Array Into Arrays With Max Difference

info

풀이 키워드​

스포주의

정렬 그리디


풀이 코드​

info
  • 메모리: 59600 KB
  • 시간: 22 ms
class Solution {
    public int[][] divideArray(int[] nums, int k) {
        Arrays.sort(nums);
        
        int[][] ans = new int[nums.length/3][3];
        int j = 0;
        for (int i = 0; i < nums.length; i+=3 ) {
            if (nums[i+2] - nums[i] > k) return new int[][]{};
            ans[j][0] = nums[i];
            ans[j][1] = nums[i+1];
            ans[j][2] = nums[i+2];
            ++j;
        }

        return ans;
    }
}

풀이 해설​

3의 배수개만큼 원소가 들어있는 배열 nums와 k가 주어질 때

3개씩 원소를 묶어서 배열을 나눠보고 각 배열 내 최대 차가 모두 k 이하이면 해당 상태를 리턴,

반대로 k를 초과하면 빈 배열을 리턴하면 되는 문제이다.

이는 최대한 값이 비슷한 녀석들끼리 묶어주는 것이 최선이기에, 정렬을 떠올려볼 수 있다.

for (int i = 0; i < nums.length; i+=3 ) {
    if (nums[i+2] - nums[i] > k) return new int[][]{};
    ans[j][0] = nums[i];
    ans[j][1] = nums[i+1];
    ans[j][2] = nums[i+2];
    ++j;
}

정렬을 해서 끼리끼리 묶어줬는데도 k를 초과해버리면 빈 배열로 도중에 리턴해버리면 된다.


메모​

  • 허수 medium 문제