LeetCode 768. Max Chunks To Make Sorted II(JAVA)

출처 : https://leetcode.com/problems/max-chunks-to-make-sorted-ii/description/

#문제

You are given an integer array arr.
We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.
Return the largest number of chunks we can make to sort the array.

정수 배열 arr가 주어집니다.이 배열을 여러 개의 청크(즉, 파티션)로 나눌 수 있습니다. 각 청크를 개별적으로 정렬한 후, 이 청크들을 이어 붙였을 때 정렬된 배열과 동일해야 합니다.이 조건을 만족하도록 배열을 나눌 수 있는 최대 청크 수를 반환하세요

 

접근 1)  HashTable, Sorting

배열을 파티션으로 나누기위해서는 정렬된 배열과 arr의 특정범위 [start :end] 내의 요소를 카운팅했을때 동일해야함을 이용하여 문제를 해결

ex) arr = [1,1,0,0,1] 라면 정렬된 배열은 sorted = [0,0,1,1,1] 

[0:3] 의 범위에서 

arr 과 sorted 에서 요소들의 갯수가 동일함 1:2, 0:2

[4:4] 의 범위에서

arr 과 sorted 에서 요소들의 갯수가 동일함 1:3, 0:2

 

즉, 2개의 청크로 나눌수있음

 

코드

public int maxChunksToSorted(int[] arr) {
    int[] sorted = arr.clone();
    Map<Integer,Integer> count = new HashMap<>();
    int cnt = 0;
    Arrays.sort(sorted);
    for(int i = 0; i < arr.length; i++){
        count.put(arr[i],count.getOrDefault(arr[i],0) + 1);
        count.put(sorted[i],count.getOrDefault(sorted[i],0) - 1);
        boolean flag = true;
        for(int num : count.values()){
            if(num != 0){
                flag = false;
                break;
            }
        }
        if(flag){
            cnt++;
            count.clear();
        }
    }
    return cnt;
}

 

 

접근2) PrefixMax, SuffixMin

 

특정 범위내의 최댓값보다 이후에 작은 요소가 없다면 해당범위는 하나의 파티션으로 나눌수있다는걸 이용한 풀이

ex) arr = [6,7,4,4,8,9,9]  sorted = [4,4,6,7,8,9,9]

[0:2] 까지의 max값 7

[3:6] 까지의 min값 4 ==> max[2] > min[3]

즉 [0:2], [3:6] 로나눈다면  [4,6,7] + [4,8,9,9] !=  [4,4,6,7,8,9,9]

 

[0:3] 까지의 max값 7

[4:6] 까지의 min값 8 ==> max[3] <=  min[4]

즉   [4,4,6,7] + [8,9,9]  ==  [4,4,6,7,8,9,9]

 

[0:4] 까지의 max값 8

[5:6] 까지의 min값 9 ==> max[4] <=  min[5]

즉  [4,4,6,7,8] + [9,9]  ==  [4,4,6,7,8,9,9]

 

[0:5] 까지의 max값 9

[6:6] 까지의 min값 9 ==> max[5] <=  min[6]

즉   [4,4,6,7,8] + [9] ==  [4,4,6,7,8,9,9]

 

[0:6] ==> arr원본과 같음 

즉   [4,4,6,7,8,9] ==  [4,4,6,7,8,9,9]

 

코드

public int maxChunksToSorted(int[] arr) {
    int[] prefixMax = arr.clone();
    int[] suffixMin = arr.clone();
    int cnt = 1;//기본적으로 1
    for (int i =1; i< arr.length;i++){
        prefixMax[i] = Math.max(prefixMax[i-1],prefixMax[i]);
    }
    //특정 요소이후의 최솟값을 구해야하므로 역순으로 수행
    for(int i = arr.length-2; i >= 0; i--){
        suffixMin[i] = Math.min(suffixMin[i], suffixMin[i+1]);
    }

    for (int i = 0;i < arr.length-1;i++){
        if(prefixMax[i] <= suffixMin[i+1]){
            cnt++;
        }
    }

    return cnt;
}