Leader

Mijeong Ryu·2023년 5월 28일
0

알고리즘

목록 보기
1/2
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] A = {3, 2, 3, 4, 3, 3, 3, -1};
        System.out.println(fastLeader(A));
    }

    public static int fastLeader(int[] A) {
        int n = A.length;
        int leader = -1;
        Arrays.sort(A);
        int candidate = A[n / 2];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (A[i] == candidate) {
                count++;
            }
            if (count > n / 2) {
                leader = candidate;
            }
        }
        return leader;
    }
}

이 코드는 주어진 배열 A에서 가장 많이 등장하는 요소(리더)를 찾는 fastLeader 함수를 구현합니다. 배열 A를 정렬한 후, 배열의 중간에 위치한 요소를 후보로 선정합니다. 그 후, 배열을 순회하면서 해당 후보가 얼마나 많이 등장하는지 세고, 만약 그 수가 배열의 길이의 절반을 초과하면 그 요소를 리더로 선정합니다. 만약 리더가 없다면 -1을 반환합니다.

배열을 정렬한 후, 우리는 쉽게 동일한 값의 슬라이스를 세고 더 똑똑한 방법으로 리더를 찾을 수 있습니다. 우리의 수열에서 리더가 어디에서든 발생한다면, 그것은 인덱스 n/2 (중앙 요소)에 반드시 발생한다는 것을 주목하세요. 이는 배열 전체 값의 절반보다 많은 리더 값이 수열의 중앙 요소 양쪽에 들어갈 수 없기 때문입니다. (리더는 무조건 n/2 인덱스에 발생!)

0개의 댓글