[LeetCode] 769. Max Chunks To Make Sorted

문제

0 ~ n-1의 순열 arr이 주어짐.
배열을 앞에서부터 여러 덩어리(chunk)로 자르고, 각 덩어리를 따로 정렬한 뒤 이어붙였을 때 전체가 정렬된 상태가 되어야 함.
이때 만들 수 있는 최대 덩어리 수를 구하는 문제.

[1,0,2,3,4] → [1,0] | [2] | [3] | [4] → 각각 정렬 후 이어붙이면 [0,1,2,3,4] → 답 4
[4,3,2,1,0] → 어디를 잘라도 안 됨 → 통째로 정렬해야 함 → 답 1

아이디어

정렬 결과는 항상 [0,1,...,n-1]. 즉 인덱스 i 자리엔 결국 숫자 i가 와야 함.

덩어리는 자기 안에서만 정렬되므로 숫자가 덩어리 밖으로 이동 못 함.
따라서 인덱스 i에서 자르려면 0 ~ i 구간 안에 숫자 0 ~ i가 전부 들어있어야 함.

순열이라는 조건 덕에 이 확인이 쉬움.
0 ~ i 구간엔 서로 다른 숫자가 정확히 i+1개 있음.
이 중 최댓값이 i라면, i 이하의 서로 다른 숫자 i+1개 → {0,1,...,i} 전부일 수밖에 없음 (비둘기집).
반대로 최댓값이 i보다 크면 더 큰 숫자가 섞여 있다는 뜻이라 자르면 안 됨.

자를 수 있는 지점마다 자르는 게 최선이므로, 누적 최댓값 == 인덱스인 지점의 개수가 답.

풀이

function maxChunksToSorted(arr: number[]): number {
    let chunks = 0, mx = 0;
    for (let i = 0; i < arr.length; i++) {
        mx = Math.max(mx, arr[i]);
        if (mx === i) chunks++;
    }
    return chunks;
}

검증

[1,0,2,3,4]

i	값	누적 최댓값	mx === i
0	1	1	✗
1	0	1	✓
2	2	2	✓
3	3	3	✓
4	4	4	✓

✓ 4개 → 답 4.

[4,3,2,1,0]은 시작부터 최댓값이 4라 i=4에서 딱 한 번만 성립 → 답 1.

복잡도

• 시간: O(n)
• 공간: O(1)

function maxChunksToSorted(arr: number[]): number {
    let maxChunks = 0
    let max = 0
    for(let i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i])
        if(max === i) maxChunks++
    }
    return maxChunks
};