[알고리즘/자바스크립트] Codility, Dominator 문제 풀이

Dominator

An 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 [3, 4, 3, 2, 3, -1, 3, 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

function solution(A);

that, given an 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.

 

For example, given array A such that [3, 4, 3, 2, 3, -1, 3, 3]

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

 

Write an efficient algorithm for the following assumptions:

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

 

---

 

오늘도 비교적 쉬운 난이도의 알고리즘 문제 하나를 풀어보았다.

 

(요즘 너무 어려운 알고리즘 문제로 끙끙거리다가 좌절감 느끼고 아예 포기해버리는 대신에

적당한 난이도의 문제를 꾸준히 풀려고 노력하고 있다.)

 

문제를 간단히 해석하면 이렇다.

 

숫자로 구성된 배열 A가 [3, 4, 3, 2, 3, -1, 3, 3]와 같이 주어졌다.

이 배열의 Dominator는 바로 숫자 3이다. 왜냐하면 숫자 8개 중에 5개(0, 2, 4, 6, 7번째 숫자)가 3이기 때문이다.

바로 Dominator 숫자가 존재하는 인덱스 아무거나 하나를 리턴하면 되는 문제이다.

 

즉, 배열 A의 Dominator인 숫자 3이 0, 2, 4, 6, 7번째 존재하므로 이 숫자들 중에 아무거나 하나만 리턴하면 된다.

단, Dominator가 존재하지 않는다면 -1을 리턴하면 된다.

 

배열 길이의 범위는 0~100,000이며, 배열에 들어가는 숫자의 범위는 −2,147,483,648 ~ 2,147,483,647이다.

 

 

function solution(A) {
    const counter = A.reduce((counter, current, index) => {
        counter[current] = counter[current] ? counter[current].concat(index) : [index];
        return counter;
    }, {});
    
    const sorted = Object.values(counter)
        .sort((left, right) => right.length - left.length);
    const isDominator = sorted[0].length > (A.length / 2);
    
    return isDominator ? sorted[0][0] : -1;
}

 

처음에 생각했던 방법은 이렇다.

배열을 순회하면서 counter라는 객체에 값을 저장하는데,

counter의 key로 배열의 값을 넣고 value로 배열의 index를 저장한다.

 

그러니까 즉, [3, 4, 3, 2, 3, -1, 3, 3] 배열을 순회하면

'3': [0] => counter 객체에 먼저 '3': [0]을 저장한다. (3이라는 숫자가 0번째에 있으므로)

'4': [1] => 그 다음 '4': [1]을 저장한다.

'3': [0, 2] => 그 다음 숫자 3은 counter에 이미 존재하므로 '3': [0]에 2(두 번째 숫자 3의 인덱스)를 추가한다.

...

이렇게 반복하고 나면 counter 객체는 이렇게 된다.

 

{ '3': [0, 2, 4, 6, 7], '4': [1], '2': [3], '-1': [5] }

이제 위 counter 객체의 value값만 배열로 모아서 정렬을 하는데,

각 배열의 길이를 기준으로 정렬한다.

 

[[0, 2, 4, 6, 7], [1], [3], [5]]

배열의 맨 첫번째 배열의 길이가 A 배열 길이의 절반보다 크면 Dominator이므로 그 배열의 첫번째 인덱스를 리턴한다.

만약 Dominator가 아니라면 -1을 리턴한다.

 

이 방법은 정확도 면에서는 100점을 받았지만

전체 배열을 전부 순회하고 sort를 위해 다시 한 번 순회해야하므로 효율성 점수가 낮았다.

그래서 위 방법을 개선해서 아래와 같이 풀고 통과했다.

 

 

function solution(A) {
    const counter = {};
    const standard = A.length / 2;
    
    for (var i = 0; i < A.length; i++) {
        if (counter[A[i]]) {
            counter[A[i]].push(i);
        } else {
            counter[A[i]] = [i];
        }

        if (counter[A[i]].length > standard) {
            return counter[A[i]][0];
        }
    }
    
    return -1;
}

 

A 배열을 for 문으로 순회하면서 아까와 같은 방식으로 counter 객체에 저장을 한다.

다른 점이라면 저장을 할 때마다 A 배열 길이의 절반과 비교해서 Dominator인지 아닌지 판별을 한다는 것이다.

 

만약에 순회하는 중간에 dominator를 발견하면 그 즉시 저장된 index를 리턴한다.

만약에 for문을 다 순회했다면 dominator가 없었다는 뜻이므로 -1을 리턴한다.

 

이 방법은 아주 최악의 경우에도 배열을 딱 한 번만 순회하면 되기 때문에 O(N)의 시간 복잡도를 가진다.

만약 Dominator를 빠르게 찾는다면 중간에 순회를 멈추기 때문에 최선의 경우에는 시간 복잡도가 O(N * logN)이 될 수도 있다.