Codility : Leader Dominator 풀이 Java, HashMap entrySet

문제 

Dominator coding task - Learn to Code - Codility

An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3

The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

For example, given array A such that

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3

the function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];

each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

 

A[] = 

3

4

3

2

3

-1

3

3

 

 

풀이

Codility에서 제공하는 Leader.pdf 읽어보면 좋아요.

https://codility.com/media/train/6-Leader.pdf

위에서 이야기하는 방식으로 풀어봤다. 

 

 

참고) HashMap 출력

//전체 출력 : {1=노란색, 2=빨간색, 3=파란색}
System.out.println(map); 

System.out.println(map.get(1));
		
//entrySet() 사용
for (Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}

//KeySet() 사용
for(Integer i : map.keySet()){
    System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}

 

1. Hashmap을 사용한 구현

Hashmap의 key: A의 element

value: element의 인덱스 정보들

 

- 포인트 1

2 1 1 3 배열이 있을 때 1의 갯수가 2면 전체 배열의 수를 2로 나눈 숫자와 같다. (2 == 4/2)

그래서 1은 dominator가 될 수 없고 정답은 -1이 된다.

 

import java.util.*;
import java.util.Map.Entry;

class Solution {
    public int solution(int[] A) {        
        HashMap<Integer, List<Integer>> map = new HashMap<>();

        for(int i = 0; i < A.length; i++) {
            int val = A[i];

            if(map.containsKey(val)) {
                map.get(val).add(i);
            } else {
                List<Integer> l = new ArrayList<>();
                l.add(i);
                map.put(val, l);
            }
        }

        int max = 0;
        int idx = -1;
        for (Entry<Integer, List<Integer>> entry : map.entrySet()) {
            if(entry.getValue().size() > max) {
                max = entry.getValue().size();
                idx = entry.getKey();
            }
        }

        if(max > A.length/2)
            return map.get(idx).get(0);

        return -1;
    }
}

 

 

2. Stack을 사용한 구현

위 Pdf에 명시된 방법 중 2번, 3번을 같이 사용했다.

2번은 이 배열에 dominator가 존재하는지 여부를 파악하기 위해 사용했는데

그 이유는 3번 방법을 사용하기 위한 전재조건으로 배열에 dominator가 있어야 하기 때문이다.

 

3번 방법은 stack을 사용해서 구현했다.

import java.util.Arrays;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		int[] a = { 1,2,1 };

		int res = solution(a);
		System.out.println(res);
	}

	public static int solution(int[] A) {
		Stack<Integer> s = new Stack<>();

		int res = -1;

		if(A.length==0)
			return res;
		
		int[] B = A.clone();
		
		// check
		Arrays.sort(B);
		int candidate = B[B.length/2];
		int cnt=0;
		for(int num : B)
			if(num == candidate)
				cnt++;
		
		if(cnt <= B.length/2)
			return res;

		for (int i = 0; i < A.length; i++) {
			int val = A[i];

			if (s.isEmpty()) {
				s.add(val);
				res = i;
			} else {
				if (s.peek() != val)
					s.pop();
				else {
					s.add(val);
					res = i;
				}
			}
		}

		if (s.isEmpty())
			return -1;

		return res;
	}

}