[코딜리티] codility lesson 8 Leader - Dominator 100%

그 동안의 설명이 너무 성의 없는 거 같아 좀더 자세히 써보기로 했습니다.

문제 요약.
https://app.codility.com/programmers/lessons/8-leader/dominator/
배열에서 절반이상을 차지한 값의 인덱스를 찾으세요.

원문.

A zero-indexed array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

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

The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

int solution(int A[], int N);

that, given a zero-indexed array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

Assume that:

• 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].

For example, given array A such that

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

the function may return 0, 2, 4, 6 or 7, as explained above.

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

중요부분 요약
도미네이터(Dominator)란 배열A 의 원소(값) 중 전체의 절반 이상을 차지한 원소 입니다.
이 배열의 인덱스는 0부터 시작하며 N개의 인티저 로 구성되어 있습니다.

예를 들어. 다음과 같은 배열이라고 하면
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이 됩니다. 총8개의 원소중 5개나 되기 때문입니다.

함수의 정의 는 이렇습니다.
int solution(int A[], int N);

그러니까, 배열에서 도미네이터중 하나의 배열번호(index) 를 리터하세요,
만약 도미네이터가 없다면 -1 을 리턴 하세요

주의

• N 의 범위는 [0..100,000];
• 배열 원소의 범위는 [−2,147,483,648..2,147,483,647].

복잡도

• 최악의 시간복잡도는 O(N);
• 최악의 공간복잡도는 O(1), 입력인수의 저장공간은 계산하지 않음.

풀이.

시간복잡도를 보아하니 중첩 루프를 돌리면 안된다.
공간복잡도를 보아하니 고정길이 변수만 허용 될 듯 하네요.

예외 처리 부터 하지요
배열길이가 0 일때 return -1;
배열길이가 0 보다 크고 3보다 작을때 return 0; // 왜냐하면 배열[0] 과 배열[1]은 어떤 값이 있더라도 0번 인덱스의 원소가 도미네이터가 되거든요.

class Solution { public int solution(int[] A) { // write your code in Java SE 8 if(A.length < 1){ return -1;} if(A.length < 3){ return 0;} } }

이제 도미네이터를 찾을 건데요.
int dominator = 0; // 도미네이터의 인덱스 번호 int candidate = 1; // 경쟁자의 인덱스 번호 int cntD = 1; // 도미네이터의 갯수 int cntC = 1; // 경쟁자의 갯수 int cnt = 0; // 도미네이터 갯수 평가용 for( int idx = 2 ; idx < A.length ; idx++ ){ if( A[idx] == A[dominator] ) { cntD++; } //도미네이터를 만났네 else if( A[idx] == A[candidate] ) { cntC++; } //경쟁자를 만났네 else{ //둘다 아닌겨? if( A[idx] != A[dominator] ) { cntD--; } //둘다 하나씩 뺀다. if( A[idx] != A[candidate] ) { cntC--; } //불필요한 if문 지우기 if( cntD < 0){ // 만약 도미네이터 수가 0개 이하로 내려가면 int tempRole = dominator; // 경쟁자와 도미네이터 를 교환한다. int tempCnt = cntD; dominator = candidate; cntD = cntC; candidate = tempRole; cntC = tempCnt; } if( cntC < 0){ // 만약 경쟁자 수가 0개 이하로 내려가면 candidate = idx; // 현재 값으로 경쟁자로 바꾼다 cntC = 0; // 새 경쟁자는 0부터 다시시작 } } }


도미네이터를 찾았습니다.
이제 결과를 돌려 줍니다.

dominator = (cntD < cntC) ? candidate : dominator; //도미네이터와 경쟁자중에서 cntD = (cntD < cntC) ? cntC : cntD; //더 많은 걸 도미네이터로 정함. for( int item : A){ if(item == A[dominator] ) cnt++; //도미네이터 갯수 세기 } return ( cnt > A.length/2 ) ? dominator : -1 ; //과반수 이상 이면 index 를 줌, 아님 -1


전체 코드

class Solution { public int solution(int[] A) { // write your code in Java SE 8 if(A.length < 1){ return -1;} if(A.length < 3){ return 0;} int dominator = 0; int candidate = 1; int cntD = 1; int cntC = 1; int cnt = 0; for( int idx = 2 ; idx < A.length ; idx++ ){ if( A[idx] == A[dominator] ) { cntD++; } else if( A[idx] == A[candidate] ) { cntC++; } else{ cntD--; cntC--; if( cntD < 0){ int tempRole = dominator; int tempCnt = cntD; dominator = candidate; cntD = cntC; candidate = tempRole; cntC = tempCnt; } if( cntC < 0){ candidate = idx; cntC = 0; } } } dominator = (cntD < cntC) ? candidate : dominator; cntD = (cntD < cntC) ? cntC : cntD; for( int item : A){ if(item == A[dominator] ) cnt++; } return ( cnt > A.length/2 ) ? dominator : -1 ; } }