이 문제에서는 정수 값으로 이루어진 배열이 주어지며, 배열에 포함된 모든 고유(distinct) 요소, 즉 중복을 제거한 값을 출력하는 것이 목표입니다.
예시를 통해 문제를 살펴보겠습니다.
입력: array = {1, 5, 7, 12, 1, 6, 10, 7, 5}
출력: 1 5 7 12 6 10이 문제를 해결하려면 배열의 각 요소가 유일한 값인지 확인해야 합니다. 가장 기본적인 방법은 두 개의 중첩 반복문을 사용하는 것입니다. 바깥쪽 반복문은 각 요소를 하나씩 선택하고, 안쪽 반복문은 그 앞에 있는 요소들과 비교하여 동일한 값이 이미 등장했는지 검사합니다. 동일한 값이 여러 번 존재하더라도 한 번만 출력합니다.
방법 1: 중첩 반복문 사용
아래 코드는 위에서 설명한 해결 방법의 구현 예시입니다.
#include <iostream>
using namespace std;
void printDistinctValues(int arr[], int n) {
for (int i=0; i<n; i++){
int j;
for (j=0; j<i; j++)
if (arr[i] == arr[j])
break;
if (i == j)
cout<<arr[i]<<"\t";
}
}
int main(){
int arr[] = {1, 5, 7, 12, 1, 6, 10, 7, 5};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"배열의 고유 요소 :\n";
printDistinctValues(arr, n);
return 0;
}
실행 결과
배열의 고유 요소 -
1 5 6 7 10 12
이 방법은 구현이 간단하지만 두 개의 반복문을 사용하기 때문에 시간 복잡도가 O(n²)으로 느려집니다. 데이터 크기가 커지면 비효율적일 수 있습니다.
방법 2: 정렬 활용
좀 더 개선된 방법은 정렬을 이용하는 것입니다. 배열을 정렬하면 같은 숫자들이 연속된 위치에 모이게 되므로, 인접한 요소만 비교하면서 중복을 쉽게 건너뛸 수 있습니다. 추가적인 메모리 사용도 적다는 장점이 있습니다.
아래는 해당 로직의 구현 예시입니다.
#include <bits/stdc++.h>
using namespace std;
void printDistinctElements(int arr[], int n){
sort(arr, arr + n);
for (int i=0; i<n; i++){
while (i < n-1 && arr[i] == arr[i+1])
i++;
cout<<arr[i]<<"\t";
}
}
int main(){
int arr[] = {1, 5, 7, 12, 1, 6, 10, 7, 5};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"배열의 고유 요소 :\n";
printDistinctElements(arr, n);
return 0;
}
실행 결과
배열의 고유 요소 -
1 5 6 7 10 12
정렬 기반 방식은 시간 복잡도가 O(n log n)으로, 중첩 반복문 방식보다 효율적입니다. 다만 원본 배열의 순서가 변경된다는 점은 유의해야 합니다.
방법 3: 해시 셋(unordered_set) 활용 — 가장 효율적인 방법
가장 효과적인 방법은 지금까지 방문한 요소들을 추적하는 것입니다. 배열을 한 번 순회하면서 각 요소를 해시 셋(unordered_set)에 저장하고, 아직 등장하지 않은 값인 경우에만 출력합니다. 이렇게 하면 단 한 번의 순회로 문제를 해결할 수 있어 시간 복잡도가 평균적으로 O(n)입니다.
아래 코드는 이 해결 방법의 구현 예시입니다.
#include<bits/stdc++.h>
using namespace std;
void printDistinctElements(int arr[], int n) {
unordered_set<int> visited;
for (int i=0; i<n; i++){
if (visited.find(arr[i])==visited.end()){
visited.insert(arr[i]);
cout<<arr[i]<<"\t";
}
}
}
int main () {
int arr[] = {1, 5, 7, 12, 1, 6, 10, 7, 5};
int n=7;
cout<<"배열의 고유 숫자 :\n";
printDistinctElements(arr,n);
return 0;
}
실행 결과
배열의 고유 숫자 -
1 5 7 12 6 10
해시 셋을 사용하면 원본 배열의 순서를 그대로 유지하면서 중복을 제거할 수 있다는 점이 특징입니다. 출력 결과가 입력 배열에서 값이 처음 등장한 순서와 일치하는 것을 확인할 수 있습니다.
정리
- 중첩 반복문: 구현이 간단하지만 O(n²)으로 비효율적
- 정렬 활용: O(n log n), 메모리 절약 가능하지만 원본 순서 변경됨
- unordered_set 활용: 평균 O(n)으로 가장 빠르며 원본 순서 유지 가능
상황에 따라 적절한 방법을 선택하되, 일반적으로는 해시 셋을 활용한 방법이 성능 면에서 가장 우수합니다.