크기가 N인 배열이 주어져 있으며, 배열의 모든 원소는 소수로 구성되어 있다고 가정해 보겠습니다. 우리의 과제는 배열 안에 존재하는 중복된 숫자를 찾아 제거하는 것입니다.
예제 1
입력
N = 8
arr[ ] = { 2, 2, 2, 3, 3, 3, 5, 7 }출력
2 3 5 7
설명: 주어진 소수 배열에는 '2'와 '3'이 각각 여러 번 중복되어 있습니다. 중복을 제거하면 2, 3, 5, 7만 남게 되므로 출력 결과는 2 3 5 7이 됩니다.
예제 2
입력
N = 5
arr[ ] = { 3, 2, 7, 5, 5 }출력
3 2 7 5
설명: 배열에서 '5'가 두 번 등장하여 중복되어 있습니다. 중복을 제거하면 3, 2, 7, 5가 입력된 순서대로 출력됩니다.
문제 해결 접근 방법
이 문제는 각 숫자가 이미 등장했는지 여부를 기록하는 별도의 확인용 배열을 활용하면 손쉽게 해결할 수 있습니다. 배열의 원소가 아직 방문되지 않았다면 해당 위치의 값을 '1'로 표시하고 결과 벡터에 삽입하고, 이미 방문한 원소라면 다시 삽입하지 않으면 됩니다.
크기 N과 원소들로 구성된 벡터 배열을 입력받습니다.
배열과 그 크기를 매개변수로 받는 함수 removeDuplicates(vector<int>&arr, int size)를 정의합니다.
정수 배열을 사용해 현재 원소가 이미 방문되었는지 검사합니다. 삽입 시점에 해당 원소가 방문 상태(값이 '1')라면 벡터에 추가하지 않고, 그렇지 않다면 벡터에 push 합니다.
최종적으로 반환되는 벡터에는 중복 없이 고유한 소수만 담기게 됩니다.
이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(N)으로 매우 효율적입니다.
구현 코드
#include<bits/stdc++.h>
using namespace std;
vector<int> removeDuplicates(vector<int>&arr, int size){
int num[100] ={0};
vector<int> vec;
for(int i=0;i<size;i++){
if(num[arr[i]] ==0){
num[arr[i]]=1;
vec.push_back(arr[i]);
}
}
return vec;
}
int main(){
int N= 8;
vector<int>arr={2,2,2,3,3,3,5,7};
vector<int>answer= removeDuplicates(arr,N);
for(int i=0;i<answer.size();i++){
cout<<answer[i]<<" ";
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
2 3 5 7
중복이 모두 제거되어 고유한 소수인 2, 3, 5, 7만 순서대로 출력되는 것을 확인할 수 있습니다. 이처럼 방문 여부를 기록하는 배열 하나만 추가하면 정렬이나 이중 반복문 없이도 선형 시간 안에 중복 제거를 완료할 수 있습니다.