정수로 이루어진 배열이 주어졌을 때, 배열에서 가장 많이 등장하는 요소(과반수 요소)를 찾아 반환하는 문제를 살펴보겠습니다. 예를 들면 다음과 같습니다.
입력 예시 1 −
N = 8
A[ ] = { 1, 2, 4, 3, 3, 1, 1, 5 }
출력 −
1
설명 − 주어진 정수 배열에서 가장 많이 등장하는 숫자는 '1'입니다. 따라서 출력은 '1'이 됩니다.
입력 예시 2 −
N = 6
A[ ] = { 1, 5, 4, 4, 1, 1 }
출력 −
1
설명 − 이 경우에도 가장 많이 등장하는 숫자는 '1'이므로, 출력으로 '1'을 반환할 수 있습니다.
문제 해결 접근 방법
주어진 배열에는 여러 개의 정수가 포함되어 있으며, 그중 가장 자주 등장하는 요소를 찾아야 합니다. 이 문제를 선형 시간 O(n)과 선형 공간 O(n) 안에서 해결하기 위해 해시맵(hashmap)을 활용한 접근 방식을 사용할 수 있습니다.
이 방식에서는 키(key)-값(value) 쌍으로 구성된 unordered map(STL 라이브러리)을 생성합니다. 키는 배열의 요소가 되고, 값은 해당 요소가 등장한 횟수가 됩니다. 이후 맵을 순회하면서 전체 크기의 절반(N/2)보다 많이 등장한 숫자를 찾아 결과로 반환합니다.
크기 N인 배열을 입력받습니다.
정수형 함수 maxOccurrence(int A[], int size)는 배열과 그 크기를 입력으로 받아 최대 빈도수를 가진 숫자를 반환합니다.
배열의 모든 요소를 대상으로, 키에는 요소 값을, 값에는 해당 요소의 빈도수를 저장하는 해시맵을 생성합니다.
맵을 순회하면서 어떤 요소의 빈도수가 N/2보다 큰지 확인하고, 조건을 만족하는 요소가 있으면 해당 숫자를 반환합니다. 만약 과반수 요소가 존재하지 않는다면 '-1'을 반환합니다.
예제 코드
위 알고리즘을 파이썬으로 구현한 코드는 다음과 같습니다.
def checkMajorityElement(arr, N):
mp = {}
for i in range(0, N):
if arr[i] in mp.keys():
mp[arr[i]] += 1
else:
mp[arr[i]] = 1
for key in mp:
if mp[key] > (N / 2):
return key
return -1
print("Enter size of array:")
N = int(6)
print("Enter elements of array:")
arr = [2, 1, 1, 2, 2, 2]
ans = checkMajorityElement(arr, N)
if ans != -1:
print("Majority Element is: %d" % ans)
else:
print("No majority element in array")
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Enter size of array: 6
Enter elements of array: 2 1 1 2 2 2
Majority Element is: 2
배열 {2, 1, 1, 2, 2, 2}에서 숫자 2는 총 4번 등장하며, 이는 배열 크기 6의 절반인 3보다 큽니다. 따라서 2가 과반수 요소로 판별되어 출력됩니다. 참고로 이 문제는 파이썬의 collections.Counter를 사용하면 더욱 간결하게 구현할 수도 있습니다.