21.03.08 [Codility] Dominator

[blossun]

• 문제

아이디어

key, value로 등장한 key : 숫자, value : 등장횟수를 저장하고,
저장하면서 A.length의 절반만큼 등장했다면 해당 인덱스를 반환

어려운점 & 실수

• 절반등장하는 경우가 아니라 초과해서 등장하는 경우로 카운팅해야함. ex) 배열의 길이가 6인 경우, 3번이 아니라 4번 등장해야함
• 배열의 길이가 1인 경우도 고려해야함. 무조건 절반 등장하는 경우이므로 index 0을 return

정답

import java.util.HashMap;
import java.util.Map;

public class Dominator {
    public int solution(int[] A) {
        // key, value로 등장한 key : 숫자, value : 등장횟수를 저장하고,
        // 저장하면서 A.length의 절반만큼 등장했다면 해당 인덱스를 반환
        if (A.length == 1) {
            return 0;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            int num = A[i];
            if (map.containsKey(num)) {
                int count = map.get(num) + 1;
                if (count > A.length / 2) {
                    return i;
                }
                map.put(num, count);
                continue;
            }
            map.put(num, 1);
        }
        return -1;
    }
}