[LeetCode] 769. Max Chunks To Make Sorted

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

leetcode - Max Chunks To Make Sorted

문제 유형: 그리디, 브루트 포스

문제 난이도: Medium

 

문제

You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].

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.

 

정수 n만큼의 크기를 가진 arr배열을 받는다. [0, n-1]의 수가 하나씩 있다.

최대한 이 배열을 쪼개려 한다.

나눠진 파티션들을 정렬시키고 재조합했을 때 정렬되어있도록 하는 최대 파티션 개수를 구하시오.

 

풀이

두 가지 풀이가 있다.

브루트 포스: 

왼쪽 파티션의 최대값+1이 오른쪽 파티션의 최소값과 같은 경우, 나눌 수 있다.

이를 이용해서 재귀 호출하여 완전 탐색풀이가 가능하다. n이 10 이하이므로, 시간 내로 해결된다.

 

그리디: 

i번째 인덱스까지의 최대값이 i라면, 파티션을 하나 더 나눌 수 있다.

 

코드

C++

 

브루트 포스 풀이

class Solution {
public:
    bool isDividable(int boundary, vector<int> &arr) {
        int n = arr.size();
        if(n == 2) return arr[0]+1 == arr[1];
        int lmax = -1;
        for(int i = 0; i < boundary; ++i) {
            lmax = max(lmax, arr[i]);
        }
        int rmin = 11;
        for(int i = boundary; i < n; ++i) {
            rmin = min(rmin, arr[i]);
        }

        return lmax+1 == rmin;
    }

    int solve(vector<vector<int>>& chunks) {
        int n = chunks.size();

        // for(int i = 0; i < n; ++i) {
        //     for(int j = 0; j < chunks[i].size(); ++j) {
        //         cout << chunks[i][j] << " ";
        //     }
        //     cout << "|| ";
        // }
        // cout << "\n";

        int res = 1;
        for(int j = 0; j < n; ++j) {
            auto &chunk = chunks[j];
            for(int i = 1; i < chunk.size(); ++i) {
                if(isDividable(i, chunk)) {
                    vector<vector<int>> arr;
                    for(int k = 0; k < n; ++k) {
                        if(k == j) {
                            vector<int> c1 (chunks[j].begin(), chunks[j].begin() + i);
                            vector<int> c2 (chunks[j].begin() + i, chunks[j].end());
                            arr.push_back(c1);
                            arr.push_back(c2);
                        } else arr.push_back(chunks[k]);
                    }
                    res = max(res, solve(arr) + 1);
                }
            }
        }

        return res;
    }

    int maxChunksToSorted(vector<int>& arr) {
        vector<vector<int>> nums = {arr};
        return solve(nums);
    }
};

 

 

그리디 풀이

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();

        int ans = 0;
        int maxSoFar = 0;
        for(int i = 0; i < n; ++i) {
            maxSoFar = max(maxSoFar, arr[i]);
            if(maxSoFar == i) ans++;
        }

        return ans;
    }
};