C++로 배열 속 변칙(anomaly) 개수 구하기

이 튜토리얼에서는 주어진 배열에서 변칙(anomaly)의 개수를 찾는 프로그램을 C++로 작성해 보겠습니다.

여기서 변칙이란, 어떤 숫자가 배열 내 다른 모든 숫자와의 절대 차이가 주어진 값 k보다 클 때를 의미합니다. 단 하나라도 절대 차이가 k 이하인 숫자가 존재하면 그 숫자는 변칙이 아닙니다. 예시를 통해 살펴보겠습니다.

예제

입력

arr = [3, 1, 5, 7]
k = 1

출력

4

위 예제에서 배열의 모든 숫자(3, 1, 5, 7)는 서로 간의 절대 차이가 최소 2 이상이므로, k = 1보다 항상 큽니다. 따라서 네 개의 숫자가 모두 변칙이며 결과는 4가 됩니다.

알고리즘

• 배열과 기준값 k를 초기화합니다.

• 배열의 각 요소를 순회합니다.

  • 현재 요소를 기준으로 배열 전체를 다시 한 번 순회합니다.

    • 두 숫자 간의 절대 차이를 계산합니다.

    • 절대 차이가 k 이하인 경우가 하나도 없다면, 해당 숫자를 변칙으로 판정하고 개수를 증가시킵니다.

이 알고리즘은 이중 반복문을 사용하므로 시간 복잡도는 O(n²)입니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

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

int getAnomaliesCount(int arr[], int n, int k) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        int j;
        for (j = 0; j < n; j++) {
            if (i != j && abs(arr[i] - arr[j]) <= k) {
                break;
            }
        }
        if (j == n) {
            count++;
        }
    }
    return count;
}

int main() {
    int arr[] = {3, 1, 5, 7}, k = 1;
    int n = 4;
    cout << getAnomaliesCount(arr, n, k) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

4

코드의 동작 방식을 간단히 설명하면, 외부 반복문으로 각 숫자를 선택한 뒤 내부 반복문에서 나머지 숫자들과 비교합니다. 만약 절대 차이가 k 이하인 숫자를 발견하면 즉시 반복문을 종료(break)하여 불필요한 연산을 줄이고, 끝까지 비교했음에도 조건에 걸리지 않은 경우에만 변칙으로 카운트합니다.