정수 요소로 이루어진 배열에 중복된 값이 포함되어 있고, 배열에 존재하는 서로 다른(고유한) 요소들의 빈도를 계산하여 결과를 출력하는 것이 목표입니다.
입력 − int arr[] = {1, 1, 2, 3, 4, 1, 2, 3}
출력 −
frequency of 1 is: 3 frequency of 2 is: 2 frequency of 3 is: 2 frequency of 4 is: 1
입력 − int arr[] = {2, 3, 4, 1, 5}
출력 −
frequency of 1 is: 1 frequency of 2 is: 1 frequency of 3 is: 1 frequency of 4 is: 1 frequency of 5 is: 1
프로그램에서 사용되는 접근 방식
이 문제는 여러 가지 방법으로 해결할 수 있으며, 코딩이 단순한 방법일 수도 있고 시간 복잡도 측면에서 더 효율적인 방법일 수도 있습니다. 먼저 코딩 관점에서 비교적 간단한 방법부터 살펴보겠습니다.
정수형 변수로 이루어진 배열을 생성합니다.
size() 함수를 사용하여 배열의 크기를 계산합니다.
배열과 같은 크기의 불리언(bool) 배열 check를 생성합니다.
i가 0부터 시작하여 size보다 작은 동안 반복하는 FOR 루프를 시작합니다.
루프 안에서 check[i]를 0으로 초기화합니다.
다시 i가 0부터 size보다 작은 동안 반복하는 FOR 루프를 시작합니다.
루프 안에서 check[i]가 1이면 continue로 건너뜁니다.
빈도를 저장할 변수 count를 선언하고 1로 초기화합니다.
j가 i+1부터 size까지 반복하는 FOR 루프를 시작합니다.
루프 안에서 arr[i]와 arr[j]가 같으면 check[j]를 1로 설정하고 count를 1 증가시킵니다.
count 값을 출력합니다.
또 다른 해결 방법은 다음과 같습니다.
정수형 변수로 이루어진 배열을 생성합니다.
size() 함수를 사용하여 배열의 크기를 계산합니다.
unordered_map 타입의 변수 um을 생성합니다.
i가 0부터 size까지 반복하는 FOR 루프를 시작합니다.
루프 안에서 um[arr[i]]++로 각 요소의 등장 횟수를 누적합니다.
auto x를 이용해 um 전체를 순회하는 또 다른 루프를 시작합니다.
루프 안에서 각 요소의 빈도를 출력합니다.
예제 1: 불리언 배열을 이용한 방법
#include <bits/stdc++.h>
using namespace std;
int frequency(int arr[], int size){
bool check[size];
for(int i=0;i<size;i++){
check[i] = 0;
}
for(int i=0; i<size; i++){
if(check[i]== 1){
continue;
}
int count = 1;
for(int j = i+1; j<size; j++){
if (arr[i] == arr[j]){
check[j] = 1;
count++;
}
}
cout<<"frequency of "<<arr[i]<<" is: " << count << endl;
}
}
int main(){
int arr[] = {1, 2, 3, 1, 2, 3};
//calculate the size of an array
int size = sizeof(arr) / sizeof(arr[0]);
//call function to calculate the frequency
frequency(arr, size);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
frequency of 1 is: 2 frequency of 2 is: 2 frequency of 3 is: 2
예제 2: unordered_map을 이용한 방법
#include <bits/stdc++.h>
using namespace std;
void frequency(int arr[], int size){
unordered_map<int, int> um;
for (int i = 0; i < size; i++){
um[arr[i]]++;
}
for (auto x : um){
cout<<"frequency of "<<x.first<<" is: "<< x.second<< endl;
}
}
int main(){
int arr[] = {1, 2, 3, 1, 2, 3 };
int size = sizeof(arr) / sizeof(arr[0]);
frequency(arr, size);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
frequency of 3 is: 2 frequency of 1 is: 2 frequency of 2 is: 2
시간 복잡도 비교
첫 번째 방법은 중첩 루프를 사용하므로 시간 복잡도가 O(n²)입니다. 반면 두 번째 방법은 해시 기반 자료구조인 unordered_map을 활용하기 때문에 평균적으로 O(n)의 시간 복잡도를 가지며, 데이터 크기가 클수록 훨씬 효율적입니다. 다만 unordered_map은 요소의 순서를 보장하지 않으므로, 출력 순서가 입력 순서와 다르게 나타날 수 있다는 점에 유의해야 합니다.