[codility] Dominator

Dominator

Find an index of an array such that its value occurs at more than half of indices in the array.

Task Score

100%

Correctness

100%

Performance

100%

---

 

Leader가 카테고리명이라서 뭐가..리더지...뭐지..대표값..? 이랬는데

문제를 보고 나니까 뭔 말인지 이해했다.

 

지금 이 문제에 나와 있듯이,

전체 데이터들 중에 절반 이상에 해당하는 값이 leader다.

 

그래서 원래 평소에 풀듯이~ 해서 풀었는데 53점이 나왔다 ^^..

이래서 생각을 안하고 풀면 안되지.....

 

그래서 코딜리티에서 알려주는 방법을 공부해서 새로 풀었다.ㅋㅋ

그 내용은 아래와같다.

 

x
// you can also use imports, for example:
// import java.util.*;
​
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
​
class Solution {
    public int solution(int[] A) {
        int candidate = -1;
        int answer = -1;
        int val = -1;
        int size = 0;
        int tmpVal = 0;
        int tmpAns = 0;
        int count = 0;
        
        for (int i = 0; i < A.length; i++) {
            if (size == 0) {
                size++;
                tmpVal = A[i];
                tmpAns = i;
            } else if (tmpVal != A[i]) {
                size--;
            } else {
                size++;
            }   
        }
        
        if (size > 0) {
            candidate = tmpAns;
            val = tmpVal;
        }
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] == val) {
                count++;
            }
        }
        
        if (count > A.length / 2) {
            answer = candidate;
        }
​
        return answer;
    }
}

 

0번 데이터부터 n-1번 데이터까지 토너먼트를 시킨다.

살아남는놈이 있으면 size는 0보다 커지게 된다.

 

그리고 살아남는놈의 개수가 절반 이상이면 해당 데이터는 leader이다.

 

문제에서는 해당 데이터의 인덱스 중 하나를 아무거나 반환하라고 했으니,

그 값에 해당하는 인덱스를 반환해준다.