Dominator (Codility) - Java

문제

정수값을 담는 N개의 배열 A가 주어진다. A에 존재하는 정수값이 중복으로 배열 사이즈의 절반 이상 존재하는 경우 그 정수값은 Dominator가 된다. 이 Dominator를 찾고, 이 Dominator 값인 인덱스 위치 중 하나를 출력하는 문제이다.  

 

해결 방법

중복되는 값으로 몇 개가 존재하는지 효과적으로 알 수 있도록 해시 테이블을 사용한다. 해시의 Key값에는 인덱스에 존재하는 값이 들어가고, Value값은 그 값이 존재하는 인덱스들을 담는 Vector 컨테이너가 들어간다.

 

배열 A를 순회돌며 해시 테이블에 Key값과 Value값을 넣어준다. 그 작업이 끝나면 해시 테이블에 들어간 값(Iterator)를 순회돌며 배열 A 사이즈의 절반이 넘어가는 Dominator가 존재하는지 찾는다. 

 

만약 존재한다면 그 값의 Value값(Vector)의 첫번째 원소를 정답으로 리턴한다. 만약 존재하지 않는다면 -1을 리턴한다. 

 

구현 코드는 다음과 같다.

import java.util.HashMap;
import java.util.Map;
import java.util.Vector;
class Solution {
	public int solution(int[] A) {
		int result = -1;
		// 해시 테이블 생성
		HashMap<Integer, Vector<Integer>> hm = new HashMap<Integer, Vector<Integer>>();
		// 순회돌며 Key, Value 값을 채운다.
		for(int i = 0; i < A.length; ++i) {
			if(hm.containsKey(A[i])) {
				// 이미 Key가 존재하는 경우 Value값인 Vector를 받아와
				// 해당 인덱스 값을 추가하고 해시의 Value값을 갱신한다.
				Vector<Integer> v = hm.get(A[i]);
				v.add(i);
				hm.replace(A[i], v);
			} else {
				// 해시 테이블에 존재하지 않는 Key의 경우 Vector를 새로 할당받아
				// 해당 인덱스 값을 Vector에 추가하여 해시에 넣어준다.
				Vector<Integer> v = new Vector<Integer>();
				v.add(i);
				hm.put(A[i], v);
			}
		}
		
		// 해시에 들어간 값들 중 Dominator조건에 만족하는 Key값을 찾는다.
		for(Map.Entry<Integer, Vector<Integer>> elem : hm.entrySet()) {
			if(elem.getValue().size() >= (A.length / 2) + 1) {
				// 존재하는 경우 Dominator를 값으로 하는 인덱스 위치중 첫번째 위치를 정답으로 한다.
				result = elem.getValue().get(0);
			}
		}
		return result;
	}
}