C++로 정수 리스트를 두 부분으로 나눌 수 있는지 확인하는 방법

정수로 이루어진 리스트 nums가 주어졌을 때, 이 리스트를 두 개의 비어 있지 않은 부분 리스트로 나눌 수 있는지 판단해야 합니다. 조건은 왼쪽 부분의 모든 숫자가 오른쪽 부분의 모든 숫자보다 엄격히 작아야 한다는 것입니다.

예를 들어 입력이 [6, 4, 3, 8, 10]이라면 결과는 true입니다. 왼쪽을 [6, 4, 3], 오른쪽을 [8, 10]으로 나누면 왼쪽의 모든 값(6, 4, 3)이 오른쪽의 모든 값(8, 10)보다 작기 때문입니다.

접근 방법

이 문제는 접두사 최댓값(prefix maximum)과 접미사 최솟값(suffix minimum)을 활용하면 선형 시간 O(n)에 효율적으로 해결할 수 있습니다.

핵심 아이디어는 간단합니다. 임의의 위치에서 리스트를 나눴을 때 나눌 수 있는 조건은 "왼쪽 부분의 최댓값 < 오른쪽 부분의 최솟값"입니다. 따라서 다음 두 배열을 미리 계산해 둡니다.

• left[i] : 인덱스 0부터 i까지 원소 중 최댓값
• right[i] : 인덱스 i부터 마지막 원소까지 중 최솟값

이후 각 분할 지점마다 left[i]와 right[i+1]만 비교하면 되므로 전체 탐색 없이 빠르게 답을 구할 수 있습니다.

알고리즘 단계

1. n := nums의 크기로 설정합니다.
2. 크기가 n인 배열 right와 left를 정의합니다.
3. left[0] := nums[0]
4. right의 마지막 원소 := nums의 마지막 원소
5. i := 1부터 n-1까지 순회하며 left[i] := max(left[i-1], nums[i])로 갱신합니다.
6. i := n-2부터 0까지 역순으로 순회하며 right[i] := min(right[i+1], nums[i])로 갱신합니다.
7. i := 0부터 n-2까지 순회하며 left[i] < right[i+1]을 만족하는 지점이 있으면 true를 반환합니다.
8. 모든 지점에서 조건을 만족하지 않으면 false를 반환합니다.

시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool solve(vector<int> &nums) {
        int n = nums.size();
        vector<int> right(n);
        vector<int> left(n);
        left[0] = nums[0];
        right.back() = nums.back();
        for (int i = 1; i < n; i++) {
            left[i] = max(left[i - 1], nums[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            right[i] = min(right[i + 1], nums[i]);
        }
        for (int i = 0; i < n - 1; i++) {
            if (left[i] < right[i + 1])
            return true;
        }
        return false;
    }
};
main() {
    Solution ob;
    vector<int> v = {6,4,3,8,10};
    cout << (ob.solve(v));
}

입력

{6,4,3,8,10}

출력

1

결과가 1(true)로 출력됩니다. [6, 4, 3]과 [8, 10]으로 나누면 왼쪽의 최댓값 6이 오른쪽의 최솟값 8보다 작으므로 분할 조건을 충족하기 때문입니다.