Codility Lesson 08 - EquiLeader(JAVA)

https://app.codility.com/programmers/lessons/8-leader/equi_leader/

EquiLeader coding task - Learn to Code - Codility

 

문제

- 비어있지 않은 N개의 정수들로 이루어진 배열 A가 주어진다.

- leader는 배열의 전체 개수의 반보다 더 많은 원소를 의미한다.

- equi leader란 index S( 0 <= S < N-1 )에서 A[0] ~ A[S]와 A[S+1] ~ A[N-1] 두개의 그룹에서 같은 원소가 leader인 것을 의미한다.

- 예시 : A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2

위의 예제에서는 2개의 equi leader를 찾을 수 있다.

• 0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
• 2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.

우리의 목표는 equi leader가 되는 개수를 반환하는 것이다. 따라서 예제에서는 return 2

 

제한조건

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

N은 1 ~ 100,000 사이의 정수이다.

A배열의 각각의 원소들은 −1,000,000,000 ~ 1,000,000,000 사이의 정수이다.

 

풀이

- equi leader의 개수를 세기 위해서 count 변수를 초기화하고, equi leader일 때마다 count+1

- 제한조건 1번째에 따라서 equi leader가 되려면 N이 최소 2 이상이 되어야함( N < 2 에 대한 예외처리 적용 )

- S가 될 수 있는 index들을 순회하는 for문을 활용한다.

- S에 따라서 A배열의 부분배열들을 copy하여 정렬 후 index 가운데의 값을 leader라 가정한다.

- 앞의 배열과 뒤의 배열의 각각의 leader의 값이 같은지 확인( 뒤의 leader 개수 확인 하는 로직은 for문으로 작성할 예정으로 불필요한 순회 과정을 생략하기 위해서 )

- 이 때, leader의 개수가 전체 배열 개수의 반 이상이여야 하므로, leader인지를 확인하는 로직을 작성한다.( 현재 해당하는 부분배열을 순회하면서 개수가 전체 개수/2 이상인지를 확인, 반드시 현재 leader보다 큰 값을 경우에는 break 걸리도록 - timeout 방지 )

- Arrays.copyOfRange(복사할배열,startIndex,endIndex+1), Arrays.sort() 메소드를 활용

 

예상 시간 복잡도 : for문 내부에서 또 for문을 실행하지만 적절한 break를 통해서 최악에 O(N)이 나오지 않을까 예상

 

// 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) {
        // write your code in Java SE 8
        int N = A.length;
        int equiCnt = 0;

        if( N < 2 ) return equiCnt;

        // 0 <= S < N-1
        for( int i=0; i<N-1; i++ ){

            // 앞의 배열
            int[] preArr = Arrays.copyOfRange(A,0,i+1);
            int[] suArr = Arrays.copyOfRange(A,i+1,N);

            Arrays.sort(preArr);
            Arrays.sort(suArr);

            double preHalf = preArr.length / 2.0;
            double suHalf = suArr.length / 2.0;

            int preLeader = preArr[(int)preHalf];
            int suLeader = suArr[(int)suHalf];

            // leader가 같지 않으면 바로 넘긴다( 불필요한 for문 순회 방지 )
            if( preLeader != suLeader ) continue;

            int preCnt = 0;
            int suCnt = 0;
            // 개수 검증
            for( int j:preArr ){
                if( j > preLeader ) break;
                else if( j == preLeader ) preCnt++;
            }

            if( preCnt <= preHalf ) continue;

            for( int k:suArr ){
                if( k > suLeader ) break;
                else if( k == suLeader ) suCnt++;
            }

            if( suCnt <= suHalf ) continue;

            // 여기까지 오면 preLeader == suLeader 및 leader의 조건에 모두 해당되므로
            equiCnt++;
        }

        return equiCnt;

    }
}

 

timeout error발생...

아이디어가 떠오르지 않아 구글링.. 하여 아래의 블로거님의 풀이법을 확인 후 재도전

https://lipcoder.tistory.com/208

EquiLeader (Codility) - Java

 

풀이

- 전체 A배열의 Leader가 결국에는 equi leader가 될 수 있음을 알아야함..( 예시에서도 4는 A배열의 leader이자 equi leader가 될 수 있는 원소였음.. )

- A배열의 Leader를 찾고 빈도수를 기록해놓을 배열이나 다른 자료구조( 위 블로거님은 Vector에 넣어둠 )를 선언 후 기록( 누적량으로 )

- A배열을 둘로 나눌 인덱스를 순회하면서 기록한 자료구조에서 left(pre), right( 총 누적량 - left )를 구하여 half를 만족한다면 개수 카운트 하는 방식으로

 

※ Vector와 ArrayList 비교 해놓은 블로그

https://coding-factory.tistory.com/553

[Java] 자바 Vector 사용법 & 예제 총정리

 

소스코드

// 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 extractLeader( int[] arr ){
        Arrays.sort(arr);
        int leader = arr[(int)(arr.length / 2.0)];
        return leader;
    }

    public int solution(int[] A) {
        // write your code in Java SE 8
        int N = A.length;
        int equiCnt = 0;

        if( N < 2 ) return equiCnt;

        // leader 확인
        int leader = extractLeader(Arrays.copyOf(A, N));

        // leader 빈도수를 누적할 배열 선언
        int[] countArr = new int[N];

        int count = 0;
        for( int i=0; i<N; i++ ){
            if( A[i] == leader ){
                count++;
            }
            countArr[i] = count;
        }

        // 0 <= S < N-1
        for( int i=0; i<N-1; i++ ){
            double preHalf = (i+1) / 2.0;
            double suHalf = ( N - (i+1) ) / 2.0;

            int preLeaderCnt = countArr[i];
            int suLeaderCnt = countArr[N-1] - countArr[i];

            if( preLeaderCnt > preHalf && suLeaderCnt > suHalf ){
                equiCnt++;
            }
        }

        return equiCnt;

    }
}