Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 집합의 MEX를 x로 만드는 최소 연산 횟수 구하기

문제 설명

n개의 정수로 이루어진 집합이 주어졌을 때, 원소를 삽입하거나 삭제하는 연산을 최소 횟수만큼 수행하여 집합의 MEX가 주어진 값 x와 같아지도록 만드는 것이 목표입니다.

참고 − 정수 집합의 MEX(Minimum EXcluded)란 해당 집합에 존재하지 않는 가장 작은 음수가 아닌 정수를 의미합니다. 예를 들어 집합 {0, 2, 4}의 MEX는 1이며, 집합 {1, 2, 3}의 MEX는 0입니다.

예시

n = 5, x = 3이고 배열이 {0, 4, 5, 6, 7}이라면, 필요한 최소 연산 횟수는 2번입니다.

접근 방법 및 알고리즘

  • 핵심 관찰은 다음과 같습니다. 최종 집합에는 x보다 작은 모든 원소(0부터 x-1까지)가 반드시 존재해야 하고, x 자체는 존재해서는 안 되며, x보다 큰 원소들은 MEX 계산에 영향을 주지 않습니다.
  • 따라서 초기 집합에 없는 x 미만의 원소 개수를 세어 답에 더합니다. 이는 각각 한 번의 삽입 연산으로 보완할 수 있기 때문입니다.
  • 만약 x가 초기 집합에 이미 존재한다면, x를 제거하기 위해 답에 1을 추가로 더합니다.

구현 예제 (C++)

#include <iostream>
using namespace std;

int getMinOperations(int *arr, int n, int x) {
    // k: 부족한 원소의 수 + 제거해야 할 x의 존재 여부
    int k = x, i = 0;
    while (n--) {
        if (arr[n] < x) {
            // x보다 작은 원소가 이미 존재하면 필요한 삽입 횟수 감소
            --k;
        }
        if (arr[n] == x) {
            // x가 존재하면 삭제 연산 1회 추가
            ++k;
        }
    }
    return k;
}

int main() {
    int arr[] = {0, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    cout << "Minimum required operations = "
         << getMinOperations(arr, n, x) << endl;
    return 0;
}

코드 동작 원리

변수 k는 처음에 x로 초기화되는데, 이는 0부터 x-1까지 총 x개의 원소가 모두 필요하다는 의미입니다. 배열을 순회하면서 x보다 작은 원소를 발견하면 이미 충족된 요건이므로 k를 1씩 줄이고, x와 같은 원소를 발견하면 제거 연산이 필요하므로 k를 1 증가시킵니다. 최종적으로 남은 k값이 곧 최소 연산 횟수입니다.

출력 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다 −

Minimum required operations = 2

복잡도 분석

배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.