Codility #6. Dominator

많이 쉬웠던 문제.
맨 처음에 문제를 잘 못 읽어서 dominator 가 갖고있는 모든 인덱스를 뱉어야하는줄 알고 코드를 좀 복잡하게 짰었다.

근데 문제 다시 읽어보니 아무 인덱스나 뱉어내는거라... 아주 쉽게 풀었다.

풀이법은, 우선 인덱스를 하나라도 뱉어야하니, 인덱스를 클래스에 저장해서 val 기준으로 정렬을 한다.
그렇게 되면, 만약 Dominator 가 존재한다면, N/2는 무조건 Dominator 가 되어야한다.
그리고 이제 그게 앞으로 갈 수 있고 뒤로 갈수도 있으니 앞,뒤 로 카운팅을 해준다. 그리고 그 카운팅 된 숫자가 N/2 보다 크면 Dominator 이므로 그중 index 하나만 기억하고 뱉어주면 됨.

정말정말 주의해야할 점은.... N의 사이즈를 꼭 챙겨주자.
N이 0이 되면, 무조건 dominator 가 존재하지 않으므로 -1 뱉어내주기.
이거 안챙겨서 2번 틀렸다...

무조건 코딜리티 제출하기 전에 input 값의 최소 최대 체크해서 예외체크 꼭 해줄것.

import java.util.*;
class Solution {
    public static class Node implements Comparable<Node>{
        int idx;
        int val;
        public Node(int idx, int val) {
            this.idx = idx;
            this.val = val;
        }
        @Override
        public int compareTo(Node o) {
            // TODO Auto-generated method stub
            return Integer.compare(this.val, o.val);
        }
    }
 
    public int solution(int[] A) {
        // write your code in Java SE 8
        int N = A.length;
        if(N == 0 ){
            return -1;
        }
        Node[] list = new Node[N];
        for(int i = 0; i < N; i++) {
            list[i] = new Node(i, A[i]);
        }
        Arrays.sort(list);
        int[] answer = new int[N];
        Arrays.fill(answer, Integer.MAX_VALUE);
        int count = 0;
        int dominator = list[N/2].val;
        int ans = -2;
        // 앞으로 가기
        for(int i = N/2; i >= 0; i--) {
            if(list[i].val == dominator) {
                count++;
                if(ans == -2) {
                    ans = list[i].idx;
                }
            }else {
                break;
            }
        }
        // 뒤로 가기 
        for(int i = N/2+1; i < N; i++) {
            if(list[i].val == dominator) {
                count++;
            }else {
                break;
            }
        }
        if(count > N/2) {
            return ans;
        }else {
            return -1;
        }
    }
}