LeetCode 2779. Maximum Beauty of an Array After Applying Operation(JAVA)

출처 : https://leetcode.com/problems/maximum-beauty-of-an-array-after-applying-operation/description/?envType=daily-question&envId=2024-12-11

 

#문제

You are given a 0-indexed array nums and a non-negative integer k.
In one operation, you can do the following:
Choose an index i that hasn't been chosen before from the range [0, nums.length - 1].Replace nums[i] with any integer from the range [nums[i] - k, nums[i] + k].
The beauty of the array is the length of the longest subsequence consisting of equal elements.
Return the maximum possible beauty of the array nums after applying the operation any number of times.
Note that you can apply the operation to each index only once.
A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the order of the remaining elements.

0-인덱스 배열 nums와 음이 아닌 정수 k가 주어집니다.
하나의 연산에서 다음과 같은 작업을 수행할 수 있습니다:
범위 [0, nums.length - 1] 내에서 아직 선택되지 않은 인덱스 i를 선택합니다.
nums[i]를 범위 [nums[i] - k, nums[i] + k] 내의 임의의 정수로 교체합니다.
배열의 미용(beauty)은 같은 값으로 이루어진 가장 긴 부분 수열의 길이를 의미합니다.
이 연산을 원하는 만큼 수행할 수 있을 때, 배열 nums에서 가능한 최대 미용을 반환하세요.
단, 연산은 각 인덱스에 대해 한 번만 적용할 수 있습니다

1 <= nums.length <= 10^5
0 <= nums[i], k <= 10^5

 

 

접근

이 문제는 주어진 범위 [ nums[i] - k, nums[i] + k] 가 가장많이 겹치는 곳을 구하는 문제다. 시작점과 도착지점을 알수있고 겹치는 구간의 최댓값을 구해야하므로 1차원 배열과 누적합을 이용해 문제는 풀어보았다.

 

배열 선언

int maxNum = 0;
for (int n : nums) maxNum = Math.max(maxNum, n);
int[] sum = new int[maxNum + 1];

겹치는 범위를 구해야하기때문에 배열을 선언할때의 크기는 nums에서 가장 큰 수를 기준으로 정해 모든 범위를 다룰수있도록 하였다.

 

[nums[i] - k, nums[i] + k] 마다 1씩 더해주기(이중for문,  누적합)

기본적인 방법으로는 중첩 for문을 사용하는 방식이있지만 이 방식은 효율적이지 못하다

예를 들어 [0:5] [1:5] [2:5]  [3:5] [4:5] 의 범위를 1씩 늘려주려고한다면

6+5+4+3+2 == 20번의 수행을 필요로한다. 예시의 범위가 좁고 케이스도 적어 별로 많은 수행을 필요로하지않지만 본 입력값이 많고 커질때마다 수행시간은 기하급수적으로 커질것이다.

 

이것을 해결하기위해 누적합의 개념을 사용한다. 바로 각각의 범위에서 시작지점을 +1 하고 종료지점 이후에 -1을 해준 뒤 마직막에 한번만 합을 구하는것이다

예를 들어 [0:5] 의 구간을 1로 바꾸고싶다면

0	1	2	3	4	5	6
1	0	0	0	0	0	-1

로 바꾸는 것이다 이후 좌측에서 우측으로 누적합을 구하면

0	1	2	3	4	5	6
1	1	1	1	1	1	0

와 같이 [0:5]구간이 1로 바뀐것을 볼수있다.

 

그럼  [0:5] [1:5] [2:5]  [3:5] [4:5] 를 처리해보면

0	1	2	3	4	5	6
1	1	1	1	1	1	-6

이렇게 될것이고 누적합을 구하면

0	1	2	3	4	5	6
1	2	3	4	5	6	0

와같은 결과가 나올것이다. 그리고 문제에서는 최대한 많은 수를 동일하게 많드는 갯수를 구해야하므로 위와같은 경우에는 6이 정답일 것이다.

 

이 개념은 2차원 배열에서도 사용할수있다

전체코드

class Solution {
     public int maximumBeauty(int[] nums, int k) {
        if(nums.length == 1)
            return 1;
        int max = 1;
        int maxNum = 0;
        for (int n : nums) maxNum = Math.max(maxNum, n);
        int[] sum = new int[maxNum + 1];
        for (int n : nums) {
            sum[Math.max(0,n-k)]++;
            sum[Math.min(n+k+1,maxNum)]--;
        }
        int preFixSum =0;
        for (int i = 0 ;i<maxNum+1;i++) {
            preFixSum += sum[i];
            max = Math.max(max,preFixSum);
        }


        return max;
    }
}