배열(Array)은 같은 자료형의 요소들을 모아 놓은 집합입니다. 그중 정렬된 배열(sorted array)은 요소들이 오름차순 또는 내림차순으로 저장되어 있는 배열을 의미합니다.
고유 개수(distinct count)란 서로 다른 값의 개수를 뜻하며, 절댓값 고유 개수(absolute distinct count)는 각 요소에 절댓값(부호를 제거한 값)을 적용했을 때 서로 다른 값이 몇 개인지 세는 것입니다.
이번 글에서는 정렬된 배열에서 절댓값 고유 개수를 구하는 프로그램을 작성해 보겠습니다. 즉, 배열의 각 요소에 절댓값을 취했을 때 서로 다른 값이 총 몇 개인지 계산하는 것입니다.
예를 들어 다음과 같습니다.
입력 : [-3 , 0 , 3 , 6 ] 출력 : 3
위 배열의 절댓값 중 서로 다른 값은 0, 3, 6으로 총 3개입니다. (-3과 3은 절댓값이 같으므로 하나로 셉니다.)
이 문제는 여러 가지 방법으로 해결할 수 있으며, 대표적인 두 가지 방법을 살펴보겠습니다.
방법 1 : set(집합) 활용하기
set은 항상 중복되지 않은 고유한 요소만 저장합니다. 따라서 각 요소의 절댓값을 set에 삽입하면, 동일한 값이 여러 번 등장해도 한 번만 저장됩니다. 최종적으로 set의 크기가 곧 절댓값 고유 개수가 됩니다.
알고리즘
배열과 같은 자료형의 set(unordered_set)을 생성합니다.
배열의 각 요소에 대해 절댓값을 구해 set에 삽입합니다. 중복된 값이 여러 번 나타나도 set에는 하나의 값만 저장됩니다.
모든 요소를 처리한 후 set의 크기(size)를 반환합니다. 이것이 배열 내 절댓값 기준 고유 요소의 개수입니다.
이 방법의 시간 복잡도는 평균적으로 O(n), 공간 복잡도는 O(n)입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {-3, 0, 2, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "절댓값 고유 개수 : ";
unordered_set<int> s;
for (int i = 0 ; i < n; i++)
s.insert(abs(arr[i]));
int nof = s.size();
cout << nof;
return 0;
}출력 결과
절댓값 고유 개수 : 4
배열 {-3, 0, 2, 6}의 절댓값은 각각 3, 0, 2, 6으로 모두 서로 다르므로 개수는 4가 됩니다.
방법 2 : 투 포인터와 카운트 변수 활용하기
두 번째 방법은 set처럼 추가 메모리를 사용하지 않고, 카운트 변수 하나만으로 문제를 해결합니다. 배열이 이미 정렬되어 있다는 특성을 활용하여, 양쪽 끝에서부터 두 개의 포인터(i, j)를 이동시키며 절댓값이 같은 요소들을 찾아 중복을 제거합니다.
동작 원리는 다음과 같습니다.
먼저 카운트를 전체 요소 개수(n)로 초기화합니다.
양 끝의 인접한 요소들이 서로 같으면 중복이므로 카운트를 감소시키고 포인터를 이동시킵니다.
양 끝 요소의 합이 0이면(예: -5와 5) 절댓값이 같은 쌍이므로 카운트를 1 감소시키고 양쪽 포인터를 모두 안쪽으로 이동시킵니다.
합이 음수면 왼쪽 포인터를, 양수면 오른쪽 포인터를 이동시켜 다음 값을 비교합니다.
정렬된 배열만 필요하고 추가 자료구조가 없으므로, 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 메모리 측면에서 매우 효율적입니다.
예제 코드
#include <iostream>
using namespace std;
int main() {
int arr[] = {-5, -1, 0, 5, 8};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "절댓값 고유 개수 : ";
int count = n;
int i = 0, j = n - 1, sum = 0;
while (i < j) {
while (i != j && arr[i] == arr[i + 1])
count--, i++;
while (i != j && arr[j] == arr[j - 1])
count--, j--;
if (i == j)
break;
sum = arr[i] + arr[j];
if (sum == 0) {
count--;
i++, j--;
}
else if(sum < 0)
i++;
else
j--;
}
cout << count;
return 0;
}출력 결과
절댓값 고유 개수 : 4
배열 {-5, -1, 0, 5, 8}의 절댓값은 5, 1, 0, 5, 8이며, 여기서 -5와 5가 중복되므로 서로 다른 값은 0, 1, 5, 8로 총 4개입니다.
마무리
set을 사용하는 방법은 구현이 간단하고 직관적이라는 장점이 있지만, 추가 메모리 O(n)이 필요합니다. 반면 투 포인터 방식은 정렬된 배열이라는 조건을 활용해 O(1)의 공간만으로 문제를 해결할 수 있습니다. 입력 배열이 이미 정렬되어 있다면 투 포인터 방식이, 임의의 배열이라면 먼저 정렬(O(n log n)) 후 투 포인터를 적용하거나 set을 사용하는 것이 좋습니다.