자바(Java)로 배열의 과반수 요소(Majority Element) 찾기 – HashMap 활용법

문제 개요

정수로 구성된 배열이 하나 주어져 있다고 가정해 보겠습니다. 이때 우리가 해야 할 일은 배열에서 가장 많이 등장하는 원소, 즉 과반수 요소(Majority Element)를 찾아내는 것입니다.

입력-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'을 반환할 수 있습니다.

문제 해결 접근 방식

주어진 배열에는 여러 개의 정수가 들어 있으며, 그중 가장 빈번하게 등장하는 원소를 찾아야 합니다. 이 문제는 해시맵(HashMap)을 활용하면 선형 시간 O(n), 선형 공간 O(n) 안에서 효율적으로 해결할 수 있습니다.

이 접근 방식에서는 키(key)-값(value) 쌍으로 이루어진 해시맵을 생성합니다. 이때 키는 배열의 원소가 되고, 값은 해당 원소의 등장 횟수가 됩니다. 이후 맵을 순회하며 등장 횟수가 가장 많은 숫자를 찾아 결과로 반환하면 됩니다.

• 크기가 N인 정수 배열을 입력받습니다.

• checkMajorityElement(int arr[], int N) 함수는 배열과 그 크기를 입력으로 받아 최대 빈도를 가진 숫자를 반환합니다.

• 배열의 모든 원소를 순회하면서 키를 원소로, 값을 그 빈도수로 하는 해시맵을 생성합니다.

• 맵을 순회하면서 어떤 원소의 등장 횟수가 N/2보다 크다면 해당 숫자를 결과로 반환하고, 조건을 만족하는 원소가 없다면 '-1'을 반환합니다.

자바 예제 코드

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
class Majority_Element{
    public static int checkMajorityElement(int arr[], int N){
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
        for (int i = 0; i < N; i++){
            if (mp.containsKey(arr[i]))
                mp.put(arr[i], mp.get(arr[i]) + 1);
            else
                mp.put(arr[i], 1);
        }
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()){
            if (entry.getValue() > (N / 2))
                return entry.getKey();
        }
        return -1;
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter size of array:");
        int N = 6;
        int arr[] = {2,1,1,2,2,2};
        System.out.println("Enter elements of array:");
        for (int i = 0; i < N; i++)
            arr[i] = sc.nextInt();
        int ans = checkMajorityElement(arr, N);
        if (ans != -1)
            System.out.println("Majority Element is: " + ans);
        else
            System.out.println("No majority element in array");
    }
}

실행 결과

위 코드를 실행하면 다음과 같은 출력을 확인할 수 있습니다.

Enter size of array: 6
Enter elements of array: 2 1 1 2 2 2
Majority Element is: 2

복잡도 분석

배열 전체를 한 번만 순회하므로 시간 복잡도는 O(N)이며, 각 원소의 빈도를 저장하기 위해 해시맵을 사용하므로 공간 복잡도 역시 O(N)입니다. 이처럼 해시맵을 활용하면 반복문을 중첩하지 않고도 과반수 요소를 빠르게 찾을 수 있습니다.