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

C++로 1부터 N까지의 배열에서 누락된 4개의 숫자 찾기

문제 개념

각 정수가 1부터 N 사이의 범위에 속하는 고유한(중복 없는) 정수 배열이 주어집니다. 배열의 크기는 N-4이므로, 1부터 N까지의 숫자 중 정확히 4개가 배열에 빠져 있습니다. 이때 누락된 4개의 숫자를 오름차순으로 찾아 출력하는 것이 문제의 목표입니다.

예제 1

입력:

arr[] = {3, 6, 7, 4, 9}

출력:

1 2 5 8

예제 2

입력:

arr[] = {2, 8, 4, 13, 6, 11, 9, 5, 10}

출력:

1 3 7 12

기본 접근 방식: O(N) 보조 배열

가장 간단한 방법은 크기 N짜리 보조 배열을 만들어 등장한 숫자를 표시(mark)하는 것입니다. 입력 배열을 한 번 순회하며 보조 배열에 해당 숫자의 존재를 기록한 뒤, 마지막에 표시되지 않은 인덱스를 모두 출력하면 됩니다. 시간 복잡도는 O(N)입니다.

그렇다면 O(1)의 보조 공간만으로는 어떻게 해결할 수 있을까요?

O(1) 보조 공간을 활용한 최적화 풀이

핵심 아이디어는 입력 배열 자체와 길이 4짜리 helper 배열을 활용해 방문 여부를 기록하는 것입니다.

  1. 길이가 4인 helper 배열을 선언하고 0으로 초기화합니다. 이 배열은 입력 배열의 길이보다 큰 4개의 후보 숫자(N+1 ~ N+4)의 등장 여부를 추적하는 데 사용됩니다.

  2. 입력 배열을 i = 0부터 끝까지 순회하면서 i번째 요소의 절댓값을 변수 temp에 저장한 뒤, 다음 규칙에 따라 방문 여부를 표시합니다.

    • temp가 입력 배열의 길이(n)보다 작거나 같으면, arr[temp - 1]의 부호를 음수로 바꿔 해당 숫자가 등장했음을 표시합니다.
    • temp가 n보다 크면, helper[temp % n - 1]의 값을 -1로 설정해 등장했음을 표시합니다. 나머지 연산을 통해 n을 초과하는 범위의 값을 helper 배열의 인덱스 0~3에 매핑할 수 있습니다.

  3. 순회가 끝난 후 입력 배열을 다시 확인하여 값이 여전히 양수인 인덱스 i는 (i+1)이 입력에 등장하지 않았다는 의미이므로 출력합니다.

  4. 마찬가지로 helper 배열에서 값이 0 이상인 인덱스 i는 (n+i+1)이 등장하지 않았다는 의미이므로 출력합니다.

이 방법은 음수 부호를 '방문 플래그'로 재활용하기 때문에 추가 배열 없이도 누락된 숫자를 찾을 수 있으며, 시간 복잡도 O(N)과 보조 공간 O(1)을 동시에 달성합니다.

C++ 구현 예제

// 크기가 N인 배열에서 누락된 4개의 요소를 찾는 C++ 프로그램
// (배열의 요소는 1부터 N+4 범위에 존재)
#include <bits/stdc++.h>
using namespace std;

// O(N) 시간, O(1) 보조 공간으로 누락된 4개의 숫자를 찾는 함수
void missing4(int arr[], int n) {
    // 입력 배열 길이보다 큰 4개의 후보 숫자를 추적하는 배열
    int helper[4] = {0};

    // 입력 배열을 순회하며 방문한 요소를
    // arr[] 또는 helper[]에서 음수로 표시
    for (int i = 0; i < n; i++) {
        int temp = abs(arr[i]);

        // 절댓값이 배열 길이보다 작거나 같으면
        // arr[]에 존재를 표시
        if (temp <= n)
            arr[temp - 1] *= (-1);
        // 그렇지 않으면 helper[]에 존재를 표시
        else {
            if (temp % n != 0)
                helper[temp % n - 1] = -1;
            else
                helper[n - 1] = -1;
        }
    }

    // 아직 표시되지 않은(양수인) 요소 출력
    for (int i = 0; i < n; i++)
        if (arr[i] > 0)
            cout << (i + 1) << " ";

    for (int i = 0; i < 4; i++)
        if (helper[i] >= 0)
            cout << (n + i + 1) << " ";
    return;
}

// 드라이버 코드
int main() {
    int arr[] = {2, 8, 4, 13, 6, 11, 9, 5, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    missing4(arr, n);
    return 0;
}

실행 결과

1 3 7 12

정리

이 알고리즘은 배열 요소의 부호를 방문 플래그로 활용하고, 나머지 연산으로 범위를 벗어난 값을 작은 helper 배열에 매핑함으로써 추가 메모리 사용을 최소화합니다. 결과적으로 시간 복잡도 O(N), 보조 공간 O(1)으로 누락된 4개의 숫자를 정렬된 순서로 구할 수 있습니다.