문제 링크

내 코드

0ms, 9.25MB

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        // n = 10.
        // 0 <= arr[i] < n
        int n = static_cast<int>(arr.size());
        int chk{};
        int answer{};
        for(int i{};i<n;++i) {
            chk |= 1 << arr[i];
            if(chk == (1 << (i + 1)) - 1) ++answer;
        }
        return answer;
    }
};

Solution

Approach 1: PrefixMax and SuffixMin Arrays

• 0ms, 9.35MB
• Complexity
  • Let $n$ be the size of the array arr.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

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

        // Fill the prefixMax array
        for (int i = 1; i < n; i++) {
            prefixMax[i] = max(prefixMax[i - 1], prefixMax[i]);
        }

        // Fill the suffixMin array in reverse order
        for (int i = n - 2; i >= 0; i--) {
            suffixMin[i] = min(suffixMin[i + 1], suffixMin[i]);
        }

        int chunks = 0;
        for (int i = 0; i < n; i++) {
            // A new chunk can be created
            if (i == 0 || suffixMin[i] > prefixMax[i - 1]) chunks++;
        }

        return chunks;
    }
};

GPT

아래 코드는 배열 arr를 여러 구간(청크, chunks)으로 나누어, 각 구간별로만 정렬해도 최종적으로 전체 배열이 정렬된 상태가 되도록 할 때, 만들 수 있는 최대 구간 수(청크의 개수)를 구하는 알고리즘입니다.

---

문제 개념 정리

• arr를 연속된 부분 배열(chunk)로 쪼갭니다.
• 쪼개진 각 chunk를 독립적으로 정렬했을 때, 최종적으로 arr 전체가 오름차순 정렬이 되도록 해야 합니다.
• 이때 만들 수 있는 chunk의 최대 개수를 구하는 문제입니다.

예시

예를 들어,

• arr = [2, 1, 3, 4, 4] 일 때,
  • 가능한 분할 중 하나: [2, 1] | [3, 4, 4]
    • 각 chunk를 정렬: [1, 2] | [3, 4, 4] → 합치면 [1, 2, 3, 4, 4] (정렬 완료)
  • 더 잘게 쪼개면 [2, 1] | [3] | [4, 4] 등도 가능
  • 최대 몇 덩어리로 쪼갤 수 있을까?

---

코드 분석

int maxChunksToSorted(vector<int>& arr) {
    int n = arr.size();
    vector<int> prefixMax = arr;
    vector<int> suffixMin = arr;

    // 1. prefixMax[i] : arr[0..i] 구간의 최댓값
    for (int i = 1; i < n; i++) {
        prefixMax[i] = max(prefixMax[i - 1], prefixMax[i]);
    }

    // 2. suffixMin[i] : arr[i..n-1] 구간의 최솟값
    for (int i = n - 2; i >= 0; i--) {
        suffixMin[i] = min(suffixMin[i + 1], suffixMin[i]);
    }

    // 3. 구간 나누기
    int chunks = 0;
    for (int i = 0; i < n; i++) {
        // i번째 위치에서 chunk를 끊어도 괜찮은 조건:
        // (i == 0) 이거나, suffixMin[i] > prefixMax[i - 1]
        // 즉, i 이전 구간의 최댓값 < i부터 시작하는 구간의 최솟값
        if (i == 0 || suffixMin[i] > prefixMax[i - 1]) {
            chunks++;
        }
    }

    return chunks;
}

1. prefixMax[i]: 인덱스 i까지의 최댓값

for (int i = 1; i < n; i++) {
    prefixMax[i] = max(prefixMax[i - 1], prefixMax[i]);
}

• prefixMax[i]는 arr[0]부터 arr[i]까지 중 최댓값을 저장합니다.
• 예: arr = [2, 1, 3, 4, 4]라면,
  • prefixMax = [2, 2, 3, 4, 4]

2. suffixMin[i]: 인덱스 i에서 끝까지의 최솟값

for (int i = n - 2; i >= 0; i--) {
    suffixMin[i] = min(suffixMin[i + 1], suffixMin[i]);
}

• suffixMin[i]는 arr[i]부터 arr[n-1]까지 중 최솟값을 저장합니다.
• 위 예시로 arr = [2, 1, 3, 4, 4]일 때,
  • suffixMin = [1, 1, 3, 4, 4]

3. 구간(청크) 나누기

int chunks = 0;
for (int i = 0; i < n; i++) {
    if (i == 0 || suffixMin[i] > prefixMax[i - 1]) {
        chunks++;
    }
}

• 핵심 아이디어:
  • 인덱스 i에서 chunk를 끊으려면, 그 구간(0 ~ i)의 모든 원소는 정렬 시 i 이후의 원소들과 겹치거나 교란되지 않아야 합니다.
  • 수식으로 보면, prefixMax[i]가 suffixMin[i+1] 이하라면, i에서 구간을 끊어도 정렬에 문제가 없습니다.
  • 코드에서는 suffixMin[i] > prefixMax[i - 1]를 체크하고 있습니다.
    • i번째 원소도 구간에 포함하려면, 이전 구간의 최대값이 i 이후 구간의 최솟값보다 작아야 한다는 뜻이 됩니다.
    • 여기서는 구현 편의상, “suffixMin[i] > prefixMax[i - 1]” 형태를 사용했고, 경계 처리(i == 0)도 따로 해 주었습니다.
• chunks++: 조건에 맞으면 구간을 하나 늘립니다.

---

예시 동작

arr = [2, 1, 3, 4, 4]

1. prefixMax = [2, 2, 3, 4, 4]
2. suffixMin = [1, 1, 3, 4, 4]

인덱스별로 살펴보면:

• i=0
  • i == 0 → 자동으로 chunks = 1
  • 여기서 구간을 끊으면 첫 구간은 [2]
• i=1
  • suffixMin[1] = 1, prefixMax[0] = 2
  • 1 > 2? 거짓 → 구간을 끊지 않음 (여전히 첫 구간 [2, 1])
• i=2
  • suffixMin[2] = 3, prefixMax[1] = 2
  • 3 > 2? 참 → chunks = 2
  • 두 번째 구간은 [3] (실제로는 [2,1]까지가 첫 구간이지만, i=2에서 끊어도 “[2,1] | [3]” 식으로 가능한 셈)
• i=3
  • suffixMin[3] = 4, prefixMax[2] = 3
  • 4 > 3? 참 → chunks = 3
• i=4
  • suffixMin[4] = 4, prefixMax[3] = 4
  • 4 > 4? 거짓 → 끊지 않음

최종 chunks = 3.
실제로 가능한 분할:

• [2, 1] | [3] | [4, 4]
  • 정렬 후: [1, 2] | [3] | [4, 4] → 합치면 [1, 2, 3, 4, 4] (정렬 상태)

---

결론

• prefixMax와 suffixMin 배열을 구해두면, 배열을 어디서 끊어도 정렬에 문제가 없는지를 빠르게 판별할 수 있습니다.
• suffixMin[i] > prefixMax[i-1]라는 조건은 “앞 구간의 최대값이 다음 구간의 최소값보다 작아야 서로 섞이지 않는다”는 의미입니다.
• 이 로직으로 전체 구간을 순회하면서, 최대 몇 개의 청크로 분할이 가능한지 계산할 수 있습니다.
• 시간 복잡도는 O(n)으로, 배열을 두 번 순회해 prefixMax, suffixMin을 만들고, 한 번 더 순회해 조건을 체크하면 되므로 효율적입니다.

Approach 2: Prefix Sums

• 0ms, 9.36MB
• Complexity
  • Let $n$ be the size of the array arr.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();
        int chunks = 0, prefixSum = 0, sortedPrefixSum = 0;

        // Iterate over the array
        for (int i = 0; i < n; i++) {
            // Update prefix sum of `arr`
            prefixSum += arr[i];
            // Update prefix sum of the sorted array
            sortedPrefixSum += i;

            // If the two sums are equal, the two prefixes contain the same
            // elements; a chunk can be formed
            if (prefixSum == sortedPrefixSum) {
                chunks++;
            }
        }
        return chunks;
    }
};

GPT

아래 코드는 배열 arr가 0부터 n-1까지 숫자를 정확히 한 번씩 포함하는 “0..n-1 순열(permutation)” 이라는 전제에서, 배열을 여러 구간(청크)으로 나누어 각 구간별로 정렬했을 때 최종 전체가 오름차순이 되도록 하는 최대 청크 개수를 구하는 전형적인 아이디어입니다.

---

전제: arr가 0..n-1을 포함하는 순열

코드를 이해하기 위해서는 arr가 [0, 1, 2, …, n-1] 를 모두 한 번씩 포함한다는 점이 중요합니다.

• 예를 들어 arr = [1, 0, 2, 4, 3]와 같이 순서를 섞은 형태라면, 이는 0..4(=n-1)까지 모든 수를 정확히 한 번씩 갖는 순열입니다.
• 이 문제(LeetCode 769: Max Chunks To Make Sorted 등 유사)에선 이 전제가 있어야, sortedPrefixSum += i;가 “해당 인덱스까지 정렬된 형태의 합”을 표현하게 됩니다.

---

코드 분석

int maxChunksToSorted(vector<int>& arr) {
    int n = arr.size();
    int chunks = 0, prefixSum = 0, sortedPrefixSum = 0;

    for (int i = 0; i < n; i++) {
        prefixSum += arr[i];
        sortedPrefixSum += i;   // i = 0..n-1을 순서대로 더해 나감

        if (prefixSum == sortedPrefixSum) {
            chunks++;
        }
    }
    return chunks;
}

1. prefixSum += arr[i]

   • 0번 인덱스부터 i번 인덱스까지 실제 배열 arr 원소의 합을 누적합니다.

2. sortedPrefixSum += i

   • 순열의 인덱스 i 자체를 더해, “인덱스 0부터 i까지의 합”을 계산합니다.
   • 만약 arr가 0..n-1 순열이라면, 인덱스 0부터 i까지의 원소 집합은 어떤 순서로 섞여 있어도 “0..i”라는 숫자들을 정확히 한 번씩 포함하게 될 때, 그 합이 동일합니다.
     • 예: i=3일 경우, 0 + 1 + 2 + 3 = 6
     • 만약 arr[0..3] 구간에 {0,1,2,3}가 들어 있다면, 그 합도 6

3. if (prefixSum == sortedPrefixSum) chunks++;

   • prefixSum과 sortedPrefixSum이 같다는 것은, “0~i 구간의 원소 합이 0 + 1 + … + i”와 동일하다는 뜻입니다.
   • 순열의 성질로 인해, 합이 같다는 것은 그 구간에 0..i라는 숫자들이 정확히 다 들어 있다는 의미가 됩니다.
   • 즉, arr[0..i] 구간을 독립적으로 정렬했을 때, 그 결과는 [0,1,2,...,i]가 됩니다. 따라서 이 구간을 하나의 청크로 끊어도 전체 정렬에는 문제가 없습니다.
   • 이렇게 구간을 끊은 뒤, 다음 구간(i+1 이후)도 같은 방식으로 청크를 나누어 나갈 수 있습니다.

---

간단 예시

• arr = [1, 0, 2, 4, 3] (n=5, 순열 0..4)

인덱스별 계산 흐름:

i	arr[i]	prefixSum (누적)	sortedPrefixSum (누적)	비교	chunks 증가?
0	1	1	0	1 == 0 ? (false)	X
1	0	1+0=1	0+1=1	1 == 1 ? (true)	chunks=1
2	2	1+2=3	1+2=3	3 == 3 ? (true)	chunks=2
3	4	3+4=7	3+3=6	7 == 6 ? (false)	X
4	3	7+3=10	6+4=10	10 == 10 ? (true)	chunks=3

• i=1 시점: arr[0..1] = {1,0}, 합 = 1, “0..1 합”도 1 → 분할 가능
• i=2 시점: arr[0..2] = {1,0,2}, 합 = 3, “0..2 합”도 3 → 또 분할 가능
  • 사실상 [1,0,2] 전체가 0..2의 집합이므로, 정렬 시 [0,1,2]
• i=3 시점: arr[0..3] 합 = 7, “0..3 합”= 6 → 분할 불가
• i=4 시점: arr[0..4] 합 = 10, “0..4 합”= 10 → 분할 가능 (마지막 구간)

최종 chunks = 3.

---

핵심 아이디어 요약

1. 0..n-1 순열 가정
   • 각 인덱스 i를 더한 sortedPrefixSum은 “0에서 i까지의 합”을 나타낸다.
2. 같은 합이면 그 구간은 0..i 집합
   • 즉, “arr의 0..i 구간을 오름차순 정렬하면 [0..i]가 된다”는 의미.
   • 구간을 독립적으로 정렬해도 전체 정렬 결과에 이상이 없다.
3. 최대 청크
   • 매번 prefixSum == sortedPrefixSum이 될 때마다 구간을 끊어 청크를 하나 늘린다.

이 로직 덕분에 한 번의 for 루프로 $O(n)$ 에 최대 청크 개수를 빠르게 구할 수 있습니다.

---

결론

• 배열이 0..n-1 순열일 때는, 인덱스와의 합을 이용해서 “해당 구간이 0..i까지 숫자를 모두 포함하는지”를 판별합니다.
• prefixSum == sortedPrefixSum가 되면 구간을 끊고 청크 개수를 증가시키면 됩니다.
• 이렇게 하면 “각 청크를 독립적으로 정렬했을 때 최종 배열이 전체 오름차순”을 만족하며, 동시에 구간(청크)의 개수도 최대로 만들 수 있습니다.