[LeetCode] 769. Max Chunks To Make Sorted (Python)

 

 

난이도: 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.

 

문제 예제

---

Example 1:

Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

제한 사항

---

• n == arr.length
• 1 <= n <= 10
• 0 <= arr[i] < n
• All the elements of arr are unique.

 

✏️ Solution(솔루션)

---

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        n = len(arr)
        answer = 0
        arr_permutation = ["0" for _ in range(n)]
        
        for i in range(1, n):
            arr_permutation[i] = arr_permutation[i-1]+str(i)

        now_permutation = ["" for _ in range(n)]
        for i in range(n):
            now_permutation[arr[i]] = str(arr[i])
            if ''.join(now_permutation[:i+1]) == arr_permutation[i]:
                answer += 1

        return answer

 

 

먼저 arr_permutation에 각 i번째마다 정렬된 순열을 저장했다.

(ex) 0: '0', 1: '01', 2: '012', 3: '0123', 4: '01234' ...)

 

그리고, arr의 요소를 확인하여 i번째 까지의 요소들을 가지고 arr_permutation[i]의 순열을 만들 수 있으면 answer에 +1을 해주었다.

 

다 풀고나니 굳이 순열을 직접 다 만들어 저장할 필요가 없을 것 같다. 숫자들의 합으로도 내가 구현한 방식과 비슷하게 구현할 수 있을 것 같다. (시간복잡도와 공간복잡도도 줄어들고..)

 

---

769. Max Chunks To Make Sorted