C++ 배열에서 분할 지점(Partition Point) 찾는 방법

개요

이 튜토리얼에서는 배열에서 분할 지점(partition point)을 찾는 방법을 알아봅니다. 분할 지점이란 해당 지점을 기준으로 왼쪽에 있는 모든 요소는 현재 값보다 작고, 오른쪽에 있는 모든 요소는 현재 값보다 큰 위치를 의미합니다.

예를 들어 배열 {4, 3, 5, 6, 7}이 있다면, 값 5가 분할 지점입니다. 왼쪽의 4와 3은 모두 5보다 작고, 오른쪽의 6과 7은 모두 5보다 크기 때문입니다.

문제 해결 접근 방식

다음 단계를 따라 문제를 해결할 수 있습니다.

배열을 초기화합니다.
배열의 각 요소를 순회하면서 다음을 확인합니다.
- 인덱스 0부터 i-1까지 순회하며, 모든 값이 현재 값 arr[i]보다 작은지 검사합니다.
- 인덱스 i+1부터 n-1까지 순회하며, 모든 값이 현재 값 arr[i]보다 큰지 검사합니다.
- 두 조건이 모두 만족되면 해당 값을 분할 지점으로 반환합니다.
조건을 만족하는 요소가 없으면 -1을 반환합니다.

예제 코드

위 접근 방식을 C++ 코드로 구현한 예제입니다.

#include <bits/stdc++.h>
using namespace std;

int findPartitionElement(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        bool is_found = true;
        // 왼쪽 요소들이 모두 작은지 확인
        for (int j = 0; j < i; j++) {
            if (arr[j] >= arr[i]) {
                is_found = false;
                break;
            }
        }
        // 오른쪽 요소들이 모두 큰지 확인
        for (int j = i + 1; j < n; j++) {
            if (arr[j] <= arr[i]) {
                is_found = false;
                break;
            }
        }
        if (is_found) {
            return arr[i];
        }
    }
    return -1;
}

int main() {
    int arr[] = { 4, 3, 5, 6, 7 };
    cout << findPartitionElement(arr, 5) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

배열 {4, 3, 5, 6, 7}에서 값 5를 기준으로 왼쪽 요소(4, 3)는 모두 작고, 오른쪽 요소(6, 7)는 모두 크므로 5가 분할 지점으로 반환됩니다.

시간 복잡도

이 알고리즘은 각 요소마다 배열 전체를 두 번 검사하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 매우 큰 경우에는 접두사 최대값(prefix max)과 접미사 최소값(suffix min)을 미리 계산해 두면 O(n) 시간에 최적화할 수 있습니다.

마무리

이번 튜토리얼에서는 C++를 이용해 배열의 분할 지점을 찾는 방법을 살펴보았습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.