[Codility][Leader] EquiLeader 풀이 해석

이 문제는 전체 배열에서 Leader가 존재한다면 이 배열을 둘로 나눴을 때 각각의 배열에서 Leader가 존재한다면 그 Leader는 전체 배열의 Leader와 같다는 전제를 알면 풀기가 쉽습니다. 말이 좀 어렵네요;

 

저는 그걸 알아차리지 못해 삽질을 많이 했네요 ㅎㅎ;

 

어쨋든 이 전제를 알면 풀이는 쉬워집니다. 배열의 원소를 하나하나 돌면서 Map을 사용하여 각 원소의 count를 계산하면 Leader를 알 수 있고.. 다시 배열을 처음부터 돌면서 둘로 나누어진 배열에서 각각 Leader가 존재하는지 확인하면 됩니다. 그런데 이렇게 하면 시간복잡도는 O(N)이지만 공간복잡도도 O(N)이 됩니다. 사실 이도 아주 훌륭한 복잡도이지만.. 공간복잡도가 O(1)인 코드가 있네요.

 

github.com/ZRonchy/Codility/blob/master/Lesson6/EquiLeader.java

 

class Solution {
    public int solution(int[] A) {
        if(A.length==1) {
            return 0;    
        }
        
        int value = A[0];
        int size=0;
        for(int i=0;i<A.length;i++) {
            if(size==0) {
                size++;    
                value = A[i];
            }else {
                if(A[i]==value) {
                    size++;    
                }else {
                    size--;
                }                
            }   
        }
        int candidate = -1;
        int count = 0;     
        if(size>0) {
           candidate = value;     
        }
        
        for(int i=0;i<A.length;i++) {
            if(A[i]==candidate) {
                count++;
            }    
        }

        if(count<=A.length/2) {  
            return 0;
        }
        
        int leader = candidate;
        int equiCount = 0;
        int leaderCount = 0;
        for(int i=0;i<A.length;i++) {
            if (A[i] == leader) {
                leaderCount++;    
            }
            
            if(leaderCount>(i+1)/2  && (count-leaderCount)>(A.length-i-1)/2) {
                equiCount++;    
            }
        }
        
        return equiCount;
    }
}

전체 코드는 위와 같습니다.

 

여기서 핵심적인 부분은 아래의 코드입니다.

int value = A[0];
int size=0;
for(int i=0;i<A.length;i++) {
    if(size==0) {
        size++;    
        value = A[i];
    }else {
        if(A[i]==value) {
            size++;    
        }else {
            size--;
        }                
    }   
}

int candidate = -1;
int count = 0;     
if(size>0) {
   candidate = value;     
}

for(int i=0;i<A.length;i++) {
    if(A[i]==candidate) {
        count++;
    }    
}

if(count<=A.length/2) {  
    return 0;
}

이렇게 for문으로 1번만 돌고 size가 0보다 큰 값을 가질 때 value가 Leader가 됩니다.

Leader의 정의는 원소의 전체 갯수의 절반보다 더 많이 등장하는 원소입니다.(more than)

 

먼저 간단한 경우를 보겠습니다.

A와 B는 임의의 수라고 가정하겠습니다.

 

A A A B B

for문을 돌려보면 size는 3까지 증가했다 1까지 줄어듭니다. size는 0보다 큰 값을 가지고 value는 A가 됩니다.

 

A B A B A

for문을 돌려보면 size가 계속 변하긴 하지만 최종적으로 size는 1, value는 A가 됩니다.

 

A A B B B

for문을 돌려보면 size는 2까지 증가했다 0까지 줄어듭니다. 여기서 value는 B로 변경되고 최종적으로는 size는 1이 됩니다.

 

A B C D E

그런데 이 경우를 보면 마지막에 value는 E, size는 1이 나옵니다.

그래서 for문 이후의 추가 코드에서 실제 몇 번이나 나오는지 Leader가 맞는지 확인하는 코드가 있어야 하네요.

 

Leader의 정의 자체가 원소 갯수의 1/2보다 더 많이 등장하는 수니까 저 코드가 동작하는 것 같습니다.

 

 

참고

github.com/ZRonchy/Codility/blob/master/Lesson6/EquiLeader.java

ZRonchy/Codility