Python으로 O(n) 시간·O(1) 추가 공간에 최대 반복 숫자 찾기

문제 개요

크기가 n인 배열이 있고, 배열의 모든 원소는 0부터 k-1 사이의 값이라고 가정해 보겠습니다. 여기서 k는 양의 정수이며 k ≤ n 조건을 만족합니다. 이때 이 배열에서 가장 많이 반복되는 숫자(최대 반복 숫자)를 찾아야 합니다.

예를 들어 입력이 k = 8, A = [3, 4, 4, 6, 4, 5, 2, 8]이라면 숫자 4가 세 번 등장하므로 출력은 4가 됩니다.

알고리즘 접근 방식

추가 배열이나 해시맵 같은 별도의 자료구조를 사용하지 않고 O(1)의 추가 공간만으로 문제를 해결하려면, 입력 배열 자체를 카운터로 활용하는 기법을 사용합니다.

핵심 아이디어는 다음과 같습니다.

• 각 원소 A[i]를 읽고, 인덱스 A[i] % k 위치의 값에 k를 더합니다.
• 이렇게 하면 해당 인덱스의 값이 몇 번 증가했는지가 곧 그 숫자의 등장 횟수가 됩니다.
• 원래 값은 A[i] % k로, 등장 횟수는 A[i] // k로 복원할 수 있습니다.

단계별 풀이 과정

1. n을 배열 A의 크기로 설정합니다.
2. i를 0부터 n-1까지 반복하면서 A[A[i] % k] += k를 수행합니다.
3. max_val을 A[0]으로, result를 0으로 초기화합니다.
4. i를 1부터 n-1까지 반복하면서 A[i] > max_val이면 max_val과 result를 갱신합니다.
5. 최종적으로 result를 반환합니다.

이 방식은 배열을 두 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리를 전혀 사용하지 않아 공간 복잡도는 O(1)입니다.

구현 예제

다음 Python 코드를 통해 동작 과정을 더 잘 이해할 수 있습니다.

def get_max_repeating(A, k):
    n = len(A)
    for i in range(n):
        A[A[i] % k] += k
    max_val = A[0]
    result = 0
    for i in range(1, n):
        if A[i] > max_val:
            max_val = A[i]
            result = i
    return result

A = [3, 4, 4, 6, 4, 5, 2, 8]
k = 8
print(get_max_repeating(A, k))

입력

[3, 4, 4, 6, 4, 5, 2, 8], 8

출력

4

정리

이 알고리즘은 배열의 값을 인덱스에 직접 누적하는 방식으로 빈도를 계산하기 때문에, 정렬이나 딕셔너리 없이도 선형 시간 안에 최대 반복 숫자를 구할 수 있습니다. 단, 원소 범위가 0부터 k-1로 제한된다는 전제 조건이 반드시 필요하다는 점을 기억하세요.