중복된 요소를 포함하는 배열이 주어졌을 때, 각 값이 처음 등장할 때만 곱셈에 포함시켜 배열 내 모든 고유(distinct) 요소의 곱을 계산하고 그 결과를 출력하는 것이 이 글의 목표입니다.
예시
입력: arr[] = {2, 1, 1, 2, 3, 4, 5, 5 }
출력: 120
설명: 1, 2, 5는 두 번 이상 반복되지만 첫 번째 등장만 곱셈에 포함합니다.
따라서 결과는 1 * 2 * 3 * 4 * 5 = 120이 됩니다.
입력: arr[] = {1, 10, 9, 4, 2, 10, 10, 45, 4 }
출력: 32400
설명: 10과 4가 반복되지만 첫 번째 등장만 곱셈에 포함합니다.
따라서 결과는 1 * 10 * 9 * 4 * 2 * 45 = 32400이 됩니다.프로그램에 사용된 접근 방식
- 중복 요소가 포함된 배열을 입력받습니다.
- 배열 요소를 오름차순으로 정렬하면 어떤 요소가 반복되는지 쉽게 파악할 수 있어 곱 계산 시 중복을 제외하기 편리합니다.
- unordered_set과 같은 해시 기반 자료구조를 활용해 이미 처리한 값을 추적하면서 모든 고유 요소를 찾아 곱해 나갑니다.
- 배열 내 모든 고유 요소의 곱을 최종 결과로 출력합니다.
알고리즘
시작
1단계 -> 배열 내 모든 고유 요소의 곱을 구하는 함수 선언
int find_Product(int arr[], int size)
int prod = 1 로 선언 및 초기화
unordered_set<int> s 변수 생성
반복문 For i = 0; i < size; i++
IF s.find(arr[i]) == s.end() (집합에 값이 없는 경우)
prod *= arr[i]
s.insert(arr[i]) 호출
End
End
return prod
2단계 -> main() 함수에서
int arr[] = { 2, 1, 1, 2, 3, 4, 5, 5 } 선언 및 초기화
배열 크기 계산: int size = sizeof(arr) / sizeof(int)
find_Product(arr, size) 호출
종료
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 중복되지 않은 요소들의 곱을 계산하는 함수
int find_Product(int arr[], int size) {
int prod = 1;
unordered_set<int> s;
for (int i = 0; i < size; i++) {
if (s.find(arr[i]) == s.end()) {
prod *= arr[i];
s.insert(arr[i]);
}
}
return prod;
}
int main() {
int arr[] = { 2, 1, 1, 2, 3, 4, 5, 5 };
int size = sizeof(arr) / sizeof(int);
cout<<"product of all non-repeated elements are : "<<find_Product(arr, size);
return 0;
}
실행 결과
product of all non-repeated elements are : 120
동작 원리
위 코드는 unordered_set(해시 기반 집합)을 사용해 이미 곱셈에 포함된 값을 추적합니다. 배열을 순회하면서 현재 요소가 집합에 존재하지 않으면 곱에 포함하고 집합에 추가하며, 이미 존재하는 값이라면 건너뜁니다. 이 방식은 정렬 없이도 중복을 효율적으로 걸러낼 수 있으며, 평균적으로 O(n)의 시간 복잡도로 빠르게 동작합니다.