문제 개요
정수(int) 요소로 구성된 배열이 주어졌을 때, 배열의 요소들을 내림차순으로 정렬하여 출력하고, 각 숫자가 몇 번 등장했는지 빈도수(occurrence)를 함께 계산하는 것이 목표입니다.
입력 : arr[]={1,1,1,2,2,2,3,3,4,5,6,7,7}
출력 : 7 occurs: 2
6 occurs: 1
5 occurs: 1
4 occurs: 1
3 occurs: 2
2 occurs: 3
1 occurs: 3
위 예시처럼 가장 큰 값인 7부터 가장 작은 값인 1까지 내림차순으로 출력하면서, 각 숫자가 배열에 나타난 횟수를 옆에 함께 표시합니다.
알고리즘
이 알고리즘은 배열이 이미 오름차순으로 정렬되어 있다는 전제 하에 동작합니다. 배열의 끝(가장 큰 값)에서부터 역방향으로 탐색하며, 인접한 두 요소의 값이 달라지는 지점을 기준으로 같은 값을 가진 그룹을 나누고, 그룹의 크기를 빈도수로 계산합니다.
시작 1단계 -> 정렬된 순서로 요소가 담긴 배열을 입력받는다 2단계 -> sizeof(a)/sizeof(a[0]) 연산으로 배열의 크기를 계산한다 3단계 -> 배열의 크기를 변수 en에 저장한다 4단계 -> i=siz-1부터 i>0이 될 때까지 1씩 감소시키며 반복한다 만약 a[i]!=a[i-1]이라면 to = en - i 로 설정한다 a[i]와 to를 출력한다 en = i 로 갱신한다 조건 종료 5단계 -> 마지막으로 a[0]과 to를 출력한다 종료
동작 원리
- en 변수는 현재 처리 중인 그룹의 끝 경계(다음에 처리할 위치)를 나타냅니다.
- 배열을 뒤에서 앞으로 순회하다가
a[i]와a[i-1]의 값이 서로 다르면, 인덱스 i부터 en-1까지의 요소들은 모두 같은 값이라는 의미입니다. - 따라서 해당 값의 빈도수는
to = en - i로 간단히 계산할 수 있습니다. - 그룹 하나를 처리할 때마다
en = i로 갱신하여 다음 그룹의 경계를 새로 설정합니다. - 반복문이 종료되면 아직 처리하지 않은 첫 번째 요소
a[0]의 빈도수(to = en)를 마지막으로 출력합니다.
C 언어 구현 예제
#include<stdio.h>
int main() {
int a[]={1,1,1,2,2,2,3,3,4,5,6,7,7};
int siz,i,en,st,to;
siz=sizeof(a)/sizeof(a[0]);
en=siz;
for(i=siz-1;i>0;i--) {
if(a[i]!=a[i-1]) {
to=en-i;
printf("%d occurs: %d\n",a[i],to);
en=i;
}
}
to=en;
printf("%d occurs: %d\n",a[0],to);
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
7 occurs: 2 6 occurs: 1 5 occurs: 1 4 occurs: 1 3 occurs: 2 2 occurs: 3 1 occurs: 3
마무리
이 방식은 정렬된 배열에서 단 한 번의 순회(O(n))만으로 각 요소의 빈도수를 구할 수 있어 매우 효율적입니다. 만약 배열이 정렬되어 있지 않다면, 먼저 qsort()와 같은 정렬 함수로 배열을 오름차순 정렬한 뒤 위 알고리즘을 적용하면 됩니다.