[Javascript] Lesson 8 - EquiLeader

 

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

 

문제 요약:

• N개의 정수로 이루어진 배열 A가 주어진다.
• 전체의 과반 수를 초과하면 리더로 선출한다.
• 인덱스 S의 범위가 0 이상 N 미만이라고 했을 때, A배열을 A[0] ~ A[S], A[S + 1] ~ A[N − 1] 로 자르고, 양쪽에서 리더를 선출했을 때 각 리더가 동일한 정수인 경우의 수를 구하여라.

 

시도 1:

function solution(A) {
    let lLeader = undefined;
    let lDomin = {};
    let rDomin = {};
    let equiLeaderCnt = 0;

    // 배열A에 포함된 각 정수의 개수 저장
    for (let i = 0; i < A.length; i++) {
        rDomin[A[i]] = rDomin[A[i]] ? rDomin[A[i]] + 1 : 1;
    };

    for (let i = 0; i < A.length; i++) {
    	// lDomin에 정수가 없으면 value로 1, 있으면 카운팅 1
        lDomin[A[i]] = lDomin[A[i]] ? lDomin[A[i]] + 1 : 1;
        
        // lLeader 선출
        lLeader = lDomin[lLeader] > lDomin[A[i]] ? lLeader : A[i];
        
        // lDomin에 A[i]을 하나 추가했으므로 rDomain에서는 하나 제거
        rDomin[A[i]]--;

        // rDomin에서 lLeader와 같은 정수 개수가 rDomin의 반 이상이면 equiLeader 개수 카운팅
        if (rDomin[lLeader] > (A.length - i - 1) / 2) {
            equiLeaderCnt++;
        };
    };

    return equiLeaderCnt;
};

위 풀이를 글로 간단히 설명하자면, A 배열에 속한 정수의 개수를 객체(rDomin)에 저장한다. 그 후 A 배열의 맨 처음부터 끝까지 다시 한 번 순환하면서, 객체 lDomin에 i번째 정수 A[i]를 더하고 lDomin 객체에 추가한 정수 A[i]를 rDomin에서 제거한다. lDomin에서 lLeader를 선출하고 해당 값이 rDomin에서도 과반수 이상을 차지하는지 확인 후 맞다면 equiLeaderCnt를 카운팅한다.

이 방법은 lLeader가 lDomin의 절반 이상을 차지하는지 판별하지 않는다는 허점이 있기 때문에 정확한 답을 구할 수 없었고, 정확도와 퍼포먼스 모두 낮은 점수를 받았다.

 

 

시도 2:

function solution(A) {
    let lLeader = null;
    let lDomin = {};
    let rDomin = {};
    let equiLeaderCnt = 0;

    for (let i = 0; i < A.length; i++) {
        rDomin[A[i]] = (rDomin[A[i]] || 0) + 1;
    };

    for (let i = 0; i < A.length - 1; i++) {
        lDomin[A[i]] = (lDomin[A[i]] || 0) + 1;
        rDomin[A[i]] = rDomin[A[i]] - 1;

        if (lLeader === null) {
            lLeader = A[i];
        } else {
            lLeader = lDomin[lLeader] > lDomin[A[i]] ? lLeader : A[i];
        };

        // lLeader가 lDomin의 절반 이상 & rLeader가 rDomin의 절반 이상이면 equiLeaderCnt 카운팅
        if (lDomin[lLeader] > (i + 1) / 2 && rDomin[lLeader] > (A.length - i - 1) / 2) {
            equiLeaderCnt++;
        };
    };

    return equiLeaderCnt;
};

https://app.codility.com/

equiLeaderCnt 카운팅 시 lLeader가 lDomin의 절반을 차지하는 정수인지 확인하는 코드를 추가했고 정확도와 퍼포먼스 모두 100%가 나왔다. (지금 보니 lLeader가 아니라 lCandinate라고 변수명을 바꾸는 게 더 적절한 듯... 변수명 지을 떄 좀 더 신경써야겠다!)