Codility Lesson 08 - Dominator( JAVA )

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

Dominator coding task - Learn to Code - Codility

 

문제

- N개의 정수들로 이루어진 배열 A가 주어진다.

- Dominator란 A배열 개수의 절반 이상의 개수를 가진 값을 의미한다.

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

  3은 Dominator가 된다. 이 때, A배열에서 Dominator인 3의 index 중 아무 요소의 index를 return 해라( 0, 2, 4, 6, 7 중 아무거나 )

 

제한조건

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

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

A의 각각의 요소들은 -2,147,483,648 ~ 2,147,483,647사이의 정수이다.

 

풀이

- 제한조건 2번째에 따르면 변수를 Integer를 사용해도 된다.( 사칙연산같은 계산이 없으므로 Integer 범위 안에서 가능 )

- Dominator를 찾기 위해서 정렬과 index 값을 활용

- 주어진 A배열을 copy하여 오름차순 정렬 후( 배열 B ) 가운데 있는 수를 Dominator로 가정한다.

- B 배열에서 가정된 dominator의 개수를 확인( count변수로 )

- count변수가 A.length / 2 보다큰지 확인 -> 크면 A배열을 순회하며 Dominator 과 값이 같은 인덱스를 찾아서 리턴, 아니면 -1을 리턴

- half가 A.length가 홀수 일 경우 소수가 나올 수 있음을 가정하여 half는 double로 변수 초기화

 

예상 시간복잡도 : O(N) - for문 순회

 

소스코드

// 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
        if( A.length == 0 ) return -1;

        int[] B = Arrays.copyOf(A, A.length);
        double half = A.length / 2.0;

        Arrays.sort(B);
        int candidate = B[(int)half];

        int count = 0;
        for( int i:B ){
            if( i > candidate ){
                break;
            }

            if( i == candidate ) count++;
        }

        int answer = -1;
        if( count > half ){
            for( int i=0; i<A.length; i++ ){
                if( A[i] == candidate){
                    answer = i;
                    break;
                }
            }
        }

        return answer;
    }
}