2294 - Partition Array Such That Maximum Difference Is K

info

• 문제 보기: 2294 - Partition Array Such That Maximum Difference Is K
• 소요 시간: 7분 11초
• 풀이 언어: java
• 체감 난이도: 1️⃣~2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

정렬 그리디

풀이 코드

info

• 메모리: 56540 KB
• 시간: 32 ms

class Solution {
    public int partitionArray(int[] nums, int k) {
        Arrays.sort(nums);
        
        int ans = 0;
        int n = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            if (n+k < nums[i]) {
                n = nums[i];
                ++ans;
            }
        }

        return ans+1;
    }
}

풀이 해설

서로의 차가 k 이하인 녀석들을 최대한 하나의 partition array로 묶을 때,

만들어지는 총 partition array의 최소 개수를 반환하는 문제이다.

diff 비교를 편하게 하기 위해 nums를 정렬하는 것이 유리하다.

이하 설명 생략.

메모

• 허수 medium 문제