정렬된 배열에서 절댓값이 고유한 요소 개수 세는 방법

이번 글에서는 배열에 포함된 요소들 중 절댓값이 서로 다른 요소가 몇 개인지 세는 방법을 알아보겠습니다.

예를 들어 배열에 {5, 5, 6, -5, 8, 2, -2, 1}과 같이 8개의 요소가 있다고 가정해 봅시다. 이 중 절댓값 기준으로 고유한 요소는 {5, 6, 8, 2, 1}의 5개입니다. -5와 5는 부호만 다를 뿐 절댓값이 같기 때문에 서로 다른 값으로 취급하지 않습니다.

접근 방법: Set 자료구조 활용

이 문제는 Set(집합) 자료구조를 사용하면 간단하게 해결할 수 있습니다. Set은 중복된 요소를 허용하지 않는 특성을 가지고 있어서, 배열의 각 요소를 삽입할 때 절댓값만 넣어주면 됩니다. 그러면 자동으로 중복이 제거되고, 최종적으로 Set에 남아 있는 요소의 개수가 곧 정답이 됩니다.

알고리즘

absoluteDistinctCount(arr)

begin
    define set s;
    for each element e in arr, do
        insert |e| into s
    done
    return the number of elements of s
end

C++ 구현 예제

#include<iostream>
#include<set>
#include<cmath>
using namespace std;

int absoluteDistinctCount(int arr[], int n){
    set<int> s;
    for(int i = 0; i<n; i++){
        s.insert(abs(arr[i])); // 절댓값을 Set에 삽입
    }
    return s.size();
}

main() {
    int arr[] = {5, 5, 6, -5, 8, 2, -2, 1};
    int n = (sizeof(arr))/(sizeof(arr[0]));
    cout << "Absolute Distinct Count: " << absoluteDistinctCount(arr, n);
}

실행 결과

Absolute Distinct Count: 5

정리

Set 자료구조의 중복 제거 특성과 abs() 함수를 조합하면, 별도의 정렬이나 복잡한 비교 로직 없이도 절댓값 기준의 고유 요소 개수를 손쉽게 구할 수 있습니다. 시간 복잡도는 배열의 모든 요소를 한 번씩 순회하고 Set에 삽입하므로 O(n log n) 수준입니다.