문제 개요
크기에 상관없이 중복된 요소를 포함할 수 있는 정렬되지 않은 배열이 주어지며, 우리의 과제는 이 배열에서 고유(distinct) 요소의 개수를 계산하는 것입니다.
배열(array)은 동일한 자료형의 요소들을 고정된 크기로 순차적으로 저장할 수 있는 가장 기본적인 자료구조입니다. 여러 데이터를 하나의 컬렉션으로 저장할 수 있으며, 같은 타입의 변수들이 모인 집합이라고 생각하면 더 쉽게 이해할 수 있습니다.
예시
입력 : int arr[] = {1, 1, 2, 3, 3, 4, 4}
출력 : count is 4
설명 : 주어진 배열에는 1, 2, 3, 4라는 4개의 고유 요소가 존재합니다. 배열의 전체 크기는 7이지만 중복 요소가 포함되어 있으므로, 중복을 제거한 뒤 남은 요소의 개수를 세면 됩니다.
입력 : int arr[] = {1, 2, 3, 4, 5, 5, 5, 5}
출력 : count is 5
설명 : 주어진 배열에는 1, 2, 3, 4, 5라는 5개의 고유 요소가 존재합니다. 배열의 크기는 8이지만 중복을 제거하면 5개만 남습니다.
방법 1: sort() 함수를 활용한 접근
- arr[] 배열을 생성합니다.
- length() 함수를 사용해 배열의 길이를 계산합니다. 이 함수는 배열에 담긴 요소 수에 해당하는 정수값을 반환합니다.
- sort() 함수를 호출하고 배열과 배열의 크기를 인자로 전달하여 배열을 오름차순으로 정렬합니다.
- 고유 요소의 개수를 저장할 임시 변수(count)를 준비합니다.
- i를 0부터 시작해 i가 배열 크기보다 작을 때까지 for 반복문을 실행합니다.
- 반복문 내부에서 i < size-1 && arr[i] == arr[i+1] 조건을 만족하는 동안 while 반복문을 실행해 중복 요소를 건너뜁니다.
- while 반복문 안에서는 i 값을 증가시킵니다.
- for 반복문 안에서는 count 값을 1씩 증가시킵니다.
- count를 반환하고 결과를 출력합니다.
방법 2: 정렬 없이 해결하는 접근
- arr[] 배열을 생성합니다.
- length() 함수를 사용해 배열의 길이를 계산합니다.
- 고유 요소의 개수를 저장할 임시 변수(count)를 준비합니다.
- i를 1부터 시작해 i가 배열 크기보다 작을 때까지 for 반복문을 실행합니다.
- 반복문 내부에서 j를 0으로 설정하고, j가 i보다 작을 때까지 내부 for 반복문을 실행하며 j를 1씩 증가시킵니다.
- 내부 반복문에서 arr[i] == arr[j]라면 break로 반복문을 종료합니다.
- 반복문 종료 후 i == j라면 현재 요소가 앞선 요소들과 중복되지 않았다는 의미이므로 count를 1 증가시킵니다.
- count를 반환하고 결과를 출력합니다.
예제 코드 1: 정렬을 사용하는 경우
#include <algorithm>
#include <iostream>
using namespace std;
int distinct_elements(int arr[], int n){
// 배열 정렬
sort(arr, arr + n);
// 정렬된 배열 순회
int count = 0;
for (int i = 0; i < n; i++){
// 중복 발견 시 인덱스 이동
while (i < n - 1 && arr[i] == arr[i + 1]){
i++;
}
count++;
}
return count;
}
// 메인 함수
int main(){
int arr[] = { 3, 6, 5, 8, 2, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "count is " << distinct_elements(arr, n);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
count is 6
예제 코드 2: 정렬 없이 처리하는 경우
#include <iostream>
using namespace std;
int countDistinct(int a[], int size){
int i, j, count = 1;
for (i = 1; i < size; i++){
for (j = 0; j < i; j++){
if (a[i] == a[j]){
break;
}
}
if (i == j){
count++;
}
}
return count;
}
// 메인 함수
int main(){
int a[] = { 3, 6, 5, 8, 2, 3, 4 };
int size = sizeof(a) / sizeof(a[0]);
cout << "count is " << countDistinct(a, size);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
count is 6
두 방법의 성능 비교
정렬을 활용하는 방법은 O(n log n)의 시간 복잡도를 가지는 반면, 정렬 없이 이중 반복문을 사용하는 방법은 최악의 경우 O(n²)의 시간 복잡도를 가집니다. 따라서 배열의 크기가 커질수록 정렬 기반 방식이 유리합니다. 참고로 C++11 이상 환경에서는 std::unordered_set에 모든 요소를 삽입한 뒤 size()를 호출하면 평균 O(n) 시간에 고유 요소의 개수를 구할 수 있으니, 실무에서는 이 방법도 함께 고려해 보시기 바랍니다.