2779. Maximum Beauty of an Array After Applying Operation

 

 

1. 문제

 

 

 

배열과 음이 아닌 k가 주어지면 

num[i]를 -K ,+k 한 값으로 바꾼 후 모든 배열에서 최대값이면서 중복이 가장 많은 수가 아름다운 수이다.

아름다운 수의 갯수를 찾자.

 

제약사항:

• 1 <= nums.length <= 105
• 0 <= nums[i], k <= 105

 

 

 

아직 선택되지 않은 배열의 인덱스 하나를 선택함
i를 i -k , i+k 범위 내에서 임의의 정수로 교체할 떄 배열 nums의 아름다움의 최댓값 반환
아름다움이란 동일한 요소 이루어진 가장 부분 수열의 길이
그리고 최대 값이여야 한다

전체적으로 모든 수를 잡고 검사해여봐야함
그렇다면 첫번 째로 배열 안에서 k 범위만큼 빼고 더해주는 배열을 만들어주고
찾기 쉽게 인덱스 맵으로 value를 넣어주고, 그 중 모든 범위에 있는 수 중 가장 큰 걸로 배열을 만든 후
그 수를 세서 리턴

 

 

 

 

 

 

2. 풀이 과정

 

public int maximumBeauty(int[] nums, int k) {



        int length = nums.length;

        if (nums.length == 1) {
            return 1;
        }

        HashMap<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> acc = new ArrayList<>();

        for (int i = 0; i < length; i++) {

            int now = nums[i];

            for (int j = now - k; j <= now +k  ; j++) {
                acc.add(j);

                if (!map.containsKey(i)) {
                    List<Integer> list =new ArrayList<>();
                    list.add(j);
                    map.put(i, list);
                } else
                    map.get(i).add(j); // get으로 가져와서 계속 추가하는 경우는 list처럼 여러 개를 쓸 때

            }
        }


        for (Map.Entry<Integer, List<Integer>> integerListEntry : map.entrySet()) {
            System.out.println(integerListEntry);
        }

        List<Integer> all = new ArrayList<>();
        for (List<Integer> value : map.values()) {

            for (Integer i : value) {
                all.add(i);

            }
        }
        Collections.sort(all);





        int max = 0;
        int count = 1;


        for (int i = 0; i < all.size() -1; i++) {

            if (all.get(i).equals(all.get(i + 1))) {
                count++;

            } else
                count = 1;

            if (max < count) {
                max = count;
            }
        }

        return max;
//        return 1;

    }

 

 

뭔가 슬라이딩 윈도우를 활용할 수 있을 거 같으나, 일단은 먼저 풀어보자

 

Hashmap으로 각각의 유효 범위를 인덱스를 키 값으로 value를 리스트로 다 넣어줄 생각이였다.

모든 value를 모아 가장 많이 중복되면서 가장 큰 수의 갯수를 찾아 return 할 생각

 

 

 

 

 

 

 

 

2-1 haspmap에 인덱스 별 유효범위 넣기

 

 

map에 키는 상관 없으니 그냥 index로 잡아주고, 

넣을 value는 j의 범위는 -k, +k 한 값으로 넣어준다.

 

 

 

i의 키가 없다면

(새로 들어왔다면 빈 list를 만들고 현재 j 값을 추가함

 

i가 키에 있다면

증가된 수일테니 그 수를 바로 리스트에 넣어줌

 

 

 

 

예를 들어 배열이 4,6,1,2의 값이 들어오고, k가 2라면

 

0번 째 인덱스는  2 ~ 6,

1번 째 인덱스는   4 ~ 8,

2번 째 인덱스는 -1 ~ 3,

3번 째 인덱스는  0 ~ 4 의 범위를 가진다.

 

 

 

 

 

2-2 한 배열에 모든 value 담기

 

 

 

map을 돌면서 value의 값들을 all에 추가 후 정렬한다.

 

배열의 value가 다 추가된다.

사실 이렇게 되면 그냥 2중 for문 하나로 처음부터 map 없이 list를 그냥 만들면 되지 않았을까?..

 

(어차피 틀려서 좀 있다 수정 때 첨부하겠따.

 

정렬된 모든 수가 담긴 배열

 

 

 

 

2-3. list의 갯수 count

 

 

그 현재 수와 다음 수를 비교해서 있다면 +1로 카운팅 해준다.

다르다면 새로운 수니까 count를 초기화해주고, max보다 커질 시 max에 저장해줌

 

 

 

 

2-4 실패

 

 

 

실패 이유!

 

 

• 배열의 크기가 최대 10510^5105, 각 숫자의 값도 최대 10510^5105입니다.
• 현재 코드는 다음과 같은 시간 복잡도를 가집니다:
  1. for 루프 안에서 범위(k) 처리:
     O(n⋅k)O(n \cdot k)O(n⋅k) (각 숫자에 대해 −k-k−k부터 +k+k+k까지 반복)
  2. 중복 확인 및 정렬:
     정렬에 O(mlog⁡m)O(m \log m)O(mlogm), 중복 확인에 O(m)O(m)O(m), 여기서 mmm은 all 리스트의 크기.

따라서 입력 크기가 10510^5105일 때, O(n⋅k)O(n \cdot k)O(n⋅k)와 O(mlog⁡m)O(m \log m)O(mlogm)는 실행 시간 초과를 초래할 수 있습니다.

 

 

 

 

아직 시간 복잡도를 정확하게 계산하는 방법이 부족하다..

 

 

 

 

 

3. 좀 더 깔끔하게 줄여보기

int length = nums.length;


int size = length * ((k *2) +1);
int[] all = new int[size];
int current = 0;

for (int i = 0; i < length; i++) {

    int now = nums[i];

    for (int j = now - k; j <= now +k  ; j++) {

        all[current++] = j;


    }
}


Arrays.sort(all);

int max = 1;
int count = 1;


for (int i = 0; i < all.length -1; i++) {

    if (all[i] == all[i + 1]) {

        count++;

    } else {
        count = 1;
    }

    if (max < count) {
        max = count;
    }
}

return max;
}

 

 

로직은 같다

 

쓸데 없는 map이랑 list를 다 줄였으나,,

 

 

 

 

 

 

4 . 슬라이딩 윈도우 사용

 

// 각 숫자에 대해 [num - k, num + k] 범위로 변환
    for (int i = 0; i < nums.length; i++) {
        nums[i] -= k; // 최소값
    }

    System.out.println(Arrays.toString(nums));

    // 정렬
    Arrays.sort(nums);

    int maxBeauty = 0;
    int left = 0;

    // 슬라이딩 윈도우로 범위 내 숫자 계산
    for (int right = 0; right < nums.length; right++) {
        // 오른쪽 포인터가 범위를 벗어나면 왼쪽 포인터 이동
        while (nums[right] > nums[left] + 2 * k) {
            left++;
        }
        // 현재 윈도우 크기 계산
        maxBeauty = Math.max(maxBeauty, right - left + 1);
    }

    return maxBeauty;
}

 

 

 

 

4-1 . 최소 값 기준

 

 

이건 정렬 전이긴 하다.. 참고

 

 

최소 값을 기준으로 ㅅ 슬라이딩 윈도우의 시작점을 잡을꺼라 num배열을 최소값으로 다 맞춰준 후 정렬

 

 

 

 

 

 

4-2.  슬라이딩 윈도우 활용