C++ 배열 요소 빈도 계산: O(n) 시간, O(1) 추가 공간으로 구현하는 방법

문제 개요

값이 1부터 n 사이인 정수 배열이 주어집니다. 일부 요소는 여러 번 반복되어 나타나고, 일부 요소는 아예 존재하지 않을 수도 있습니다. 이때 O(n) 시간과 O(1)의 추가 공간만 사용하여 배열에 있는 모든 요소의 빈도를 계산하는 것이 목표입니다.

입력 예시 1

Arr[] = { 1, 2, 2, 3, 4, 4, 4, 5 }

출력 예시 1

1 → 1, 2 → 2, 3 → 1, 4 → 3, 5 → 1

설명: 가장 큰 요소는 5이며, 출력은 각 숫자가 배열에 등장한 횟수를 나타냅니다.

입력 예시 2

Arr[] = { 1, 4, 4, 5, 5, 5, 5 }

출력 예시 2

1 → 1, 2 → 0, 3 → 0, 4 → 2, 5 → 4

설명: 가장 큰 요소는 5이며, 배열에 존재하지 않는 숫자는 빈도가 0으로 표시됩니다.

알고리즘 접근 방식

아래 프로그램은 1부터 10 사이의 숫자로 이루어진 배열에 대해 동작합니다. 핵심 아이디어는 별도의 카운터 배열 없이 입력 배열 자체를 빈도 저장소로 재활용하는 것입니다.

printfrequency(int arr[], int n) 함수는 배열과 그 크기 n을 입력받아 1~10 범위의 각 숫자가 배열에 몇 번씩 나타나는지 계산합니다.
먼저 모든 요소에서 1을 뺍니다(arr[i] = arr[i] - 1). 이렇게 하면 인덱스 i가 숫자 i+1의 빈도를 저장하는 자리가 됩니다. 즉, 숫자 1은 인덱스 0에 대응됩니다.
for 루프를 돌면서 각 요소에 대해 arr[arr[i] % 10] 위치의 값에 10을 더합니다.
숫자 i가 배열에서 x번 등장하면 해당 위치에 10이 x번 누적됩니다.
마지막으로 arr[i] / 10 값을 출력하면 인덱스 i에 대응하는 숫자 i+1의 빈도를 얻을 수 있습니다.

이 기법이 가능한 이유는 값의 범위가 10 이하로 제한되어 있기 때문입니다. 원래 값에 10씩 반복해서 더해도 % 10 연산으로 원래 값을 복원할 수 있고, 동시에 10이 더해진 횟수로 빈도를 인코딩할 수 있습니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
void printfrequency(int arr[], int n){
    int i = 0;
    // 1은 0으로, 2는 1로 ... 10은 9로 변환하여 arr[i]가 숫자 i+1의 개수를 담도록 함
    for (i = 0; i < n; i++)
        arr[i] = arr[i] - 1;
    // 숫자가 1~10 범위이므로 (num % 10 == num) 각 위치에 10을 더함
    for (i = 0; i < n; i++)
        arr[arr[i] % 10] = arr[arr[i] % 10] + 10;
    for (i = 0; i < 10; i++)
        cout << i + 1 << " -> " << arr[i] / 10 << endl;
}
int main(){
    int arr[] = {2, 3, 3, 2, 5, 6, 7, 7, 7, 8, 8, 9, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    printfrequency(arr, n);
    return 0;
}

실행 결과

1 -> 0
2 -> 2
3 -> 2
4 -> 0
5 -> 1
6 -> 1
7 -> 3
8 -> 2
9 -> 2
10 -> 0

동작 원리 단계별 분석

예제 배열 {2, 3, 3, 2, 5, 6, 7, 7, 7, 8, 8, 9, 9}의 처리 과정을 살펴보겠습니다.

1단계 (값 변환): 모든 요소에서 1을 빼면 {1, 2, 2, 1, 4, 5, 6, 6, 6, 7, 7, 8, 8}이 됩니다.
2단계 (빈도 누적): 각 값을 인덱스로 삼아 해당 위치에 10을 더합니다. 예를 들어 값 1(원래 숫자 2)은 두 번 등장하므로 arr[1]에는 20이 더해져 최종적으로 22가 됩니다.
3단계 (빈도 추출): 각 인덱스의 값을 10으로 나눈 몫이 곧 빈도입니다. arr[1]/10 = 2이므로 숫자 2는 두 번 등장한 것입니다.

복잡도 분석

시간 복잡도: O(n) — 배열을 상수 번 선형 순회합니다.
공간 복잡도: O(1) — 입력 배열 자체를 수정하여 사용하므로 추가 메모리가 전혀 필요하지 않습니다.

주의 사항

이 기법은 배열의 값이 1부터 특정 상수 범위 안에 있을 때만 적용할 수 있습니다. 값의 범위가 넓거나 음수가 포함된 경우에는 해시 맵 등 다른 방법을 사용해야 하며, 그 경우 O(1) 추가 공간 조건은 유지하기 어렵습니다.