EquiLeader (Codility) - Java

문제

N개의 숫자가 들어있는 배열 A가 주어진다. 우선 여기서 Leader 숫자를 먼저 찾는다. Leader 숫자가 되기 위해서는 두 가지 조건 중 하나가 필요하다.

1. 배열에서 가장 많이 중복되는 값

2. 배열 길이의 절반 값보다 더 많이 나오는 값

이제 A를 둘로 쪼갠다. (0 <= S < N - 1 조건을 만족하게) A[0] and A[1] ~ A[N-1],  A[0] ~ A[1] and A[2] ~ A[N-1], ...., A[0] ~ A[N - 2] and A[N - 1] 이런식으로 말이다. 그리고 쪼갠 두 부분 배열에서 Leader 숫자가 배열의 갯수 절반을 넘어가면 EquiLeader라고 할 수 있다. 문제에서 원하는 정답은 이 EquiLeader의 갯수가 총 개수이다.

 

해결 방법

우선 Leader 숫자가 무엇인지를 구해야한다. Leader 숫자를 구하기 위해 숫자들의 빈도수를 기록한다. 이때는 해쉬맵을 사용한다. A를 순회돌며 Leader 숫자를 구하면 이제 각 인덱스 별로 A가 몇 번 나왔는지 기록하기 위한 벡터를 선언한다. 그리고 A를 또 순회돌며 각 인덱스에서 Leader의 갯수가 몇 개가 나왔는지를 벡터에 기록한다.

 

벡터로 빈도수를 기록해 놨기 때문에 두 부분 배열로 쪼갤 필요 없이 벡터의 인덱스 접근으로 각 부분 배열의 빈도수가 몇개 인지 알 수 있다.

벡터 V에 기록했다고 가정하면,

0 and 1 ~ N-1 같은 경우
V[0] and V[N-1] - V[0] 

0 ~ 1 and 2 ~ N-1 같은 경우
V[1] and V[N-1] - V[1] 
...

0 ~ N-2 and N-1 같은 경우
V[N-2] and V[N-1] - V[N-2]

이런 식으로 부분 합 알고리즘을 활용해 부분 배열에서의 빈도수를 구할 수 있다. 이제 이 빈도수들이 EquiLeader 조건을 만족하는지 검사하여 정답을 구하면 된다.

 

코드로 구현하면 다음과 같다.

 

import java.util.HashMap;
import java.util.Vector;

public class Solution {
	public int solution(int[] A) {
		int result = 0;
		int leader = 0, leaderCount = 0;
		// 숫자 빈도 카운트 값 기록을 위해 해시맵 컨테이너를 선언한다.
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		// 카운트 값을 기록한다
		for(int i = 0 ; i < A.length; ++i) {
			if(hm.containsKey(A[i])) {
				int count = hm.get(A[i]);
				hm.replace(A[i], count + 1);
			} else {
				hm.put(A[i], 1);
			}
			
			// 가장 많이 나온 수 (Leader)를 기록한다.
			if(leaderCount < hm.get(A[i])) {
				leaderCount = hm.get(A[i]);
				leader = A[i];
			}
		}
		
		// Leader 숫자를 구했으니 Leader 숫자가 각 인덱스에서 
		// 몇 개 정도 나왔는지 기록할 벡터 컨테이너를 만든다.
		Vector<Integer> record = new Vector<Integer>();
		int currentCount = 0;
		// 각 인덱스위치에서 Leader의 빈도수를 기록한다.
		for(int i = 0 ; i < A.length; ++i) {
			if(A[i] == leader) {
				++currentCount;
			}
			record.add(currentCount);
		}
		
		for(int i = 0; i < A.length - 1; ++i) {
			int LeftCount = record.elementAt(i); // 둘로 쪼갰을때 왼쪽 부분 Leader 빈도수
			int RightCount = record.lastElement() - LeftCount; // 오른쪽 부분 Leader 빈도수
			
			int limitEquiLeft = ((i + 1) / 2) + 1;
			int limitEquiRight = ((A.length - (i + 1)) / 2) + 1;
			// EquiLeader 조건을 왼쪽과 오른쪽 부분 모두 만족한다면 갯수를 증가 시킨다.
			if((LeftCount >= limitEquiLeft) && (RightCount >= limitEquiRight)) {
				++result;
			}
 		}
		return result;
	}
}