주어진 문제는 배열을 원위치에서 정렬하는 것으로, 각각의 색상(0, 1, 2)을 순서대로 나열해야 합니다. 이를 위해 삼지분할법(Tripartite Partitioning)을 사용합니다.

다음은 구현 예시입니다:

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int left = -1, right = n;
        for (int i = 0; i < right;) {
            if (nums[i] == 0)
                swap(nums[++left], nums[i++]);
            else if (nums[i] == 1)
                i++;
            else
                swap(nums[--right], nums[i]);
        }
    }
};

초기화: n: 배열 길이 left: -1로 초기화, 0으로 채워질 영역을 나타냄 right: n으로 초기화, 2로 채워질 영역을 나타냄

작동 원리:

• i가 right보다 작을 때까지 반복
• nums[i]가 0이면 left와 교환하고 둘 다 증가
• nums[i]가 1이면 i만 증가
• nums[i]가 2이면 right와 교환하고 right 감소

다음 문제는 정수 배열을 오름차순으로 정렬하는 것입니다. 이를 퀵 정렬(Quick Sort) 알고리즘으로 해결할 수 있습니다.

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }

private:
    void quickSort(vector<int>& nums, int low, int high) {
        if (low >= high) return;
        int pivot = partition(nums, low, high);
        quickSort(nums, low, pivot - 1);
        quickSort(nums, pivot + 1, high);
    }

    int partition(vector<int>& nums, int low, int high) {
        int randIndex = low + rand() % (high - low + 1);
        swap(nums[high], nums[randIndex]);
        int pivot = nums[high];
        int i = low - 1;
        for (int j = low; j <= high - 1; j++) {
            if (nums[j] < pivot) {
                i++;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[high]);
        return i + 1;
    }
};

작동 원리:

• 무작위 피벗 선택 후 배열을 세 부분으로 나눔: 피벗보다 작은 값들, 같은 값들, 큰 값들
• 재귀적으로 왼쪽과 오른쪽 부분 배열 정렬

다음 문제는 주어진 배열에서 k번째로 큰 요소를 찾는 것입니다. 이를 퀵선택(Quick Select) 알고리즘으로 해결할 수 있습니다.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return quickSelect(nums, 0, nums.size() - 1, k);
    }

private:
    int quickSelect(vector<int>& nums, int low, int high, int k) {
        if (low == high) return nums[low];
        int pivotIndex = partition(nums, low, high);
        if (pivotIndex == nums.size() - k) return nums[pivotIndex];
        else if (pivotIndex > nums.size() - k) return quickSelect(nums, low, pivotIndex - 1, k);
        else return quickSelect(nums, pivotIndex + 1, high, k);
    }

    int partition(vector<int>& nums, int low, int high) {
        int randIndex = low + rand() % (high - low + 1);
        swap(nums[high], nums[randIndex]);
        int pivot = nums[high];
        int i = low - 1;
        for (int j = low; j <= high - 1; j++) {
            if (nums[j] <= pivot) {
                i++;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[high]);
        return i + 1;
    }
};

작동 원리:

• 피벗 기준으로 배열을 나누고, k번째 위치에 도달하면 해당 값을 반환
• 재귀적으로 탐색 범위 좁힘

마지막 문제는 최소한의 상품 재고량을 찾는 것입니다. 이 문제도 퀵선택 알고리즘으로 해결됩니다.

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        quickSelect(stock, 0, stock.size() - 1, cnt);
        return vector<int>(stock.begin(), stock.begin() + cnt);
    }

private:
    void quickSelect(vector<int>& stock, int low, int high, int cnt) {
        if (low >= high) return;
        int pivotIndex = partition(stock, low, high);
        if (pivotIndex == cnt - 1) return;
        else if (pivotIndex > cnt - 1) quickSelect(stock, low, pivotIndex - 1, cnt);
        else quickSelect(stock, pivotIndex + 1, high, cnt);
    }

    int partition(vector<int>& stock, int low, int high) {
        int randIndex = low + rand() % (high - low + 1);
        swap(stock[high], stock[randIndex]);
        int pivot = stock[high];
        int i = low - 1;
        for (int j = low; j <= high - 1; j++) {
            if (stock[j] <= pivot) {
                i++;
                swap(stock[i], stock[j]);
            }
        }
        swap(stock[i + 1], stock[high]);
        return i + 1;
    }
};

작동 원리:

• 주어진 재고 배열에서 가장 작은 cnt 개의 요소를 찾아 반환
• 퀵선택 알고리즘을 통해 필요한 범위 내 요소들을 배열 시작 부분에 배치