271. EquiLeader

아현·2021년 8월 16일
0

Algorithm

목록 보기
283/400



1. JavaScript

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    let count = 0;
    let rDic = {};
    let rLen = A.length;

    for(a of A){
        if (rDic.hasOwnProperty(a)){
            rDic[a]++;
        }else{
            rDic[a] = 1;
        }
    }

    let leader = 0;
    let lCount = 0;
    let lDic = {};
    let lLen = 0;

    for(a of A){
        rDic[a]--;
        rLen--;

        if(lDic.hasOwnProperty(a)){
            lDic[a]++;
        }else{
            lDic[a] = 1;
        }

        lLen++;

        if (lDic[a] > lCount){
            leader = a;
            lCount = lDic[a];
        }

        if (lCount > lLen / 2 && rDic[leader] > rLen / 2 )
        {count++;}
    }

    return count

    
}



2. Python

참고



def solution(A):

    count = 0

    right_dict = {}
    right_len = len(A)
    for a in A:
        if a in right_dict:
            right_dict[a] += 1
        else:
            right_dict[a] = 1
    
    left_leader = 0
    left_leader_count = 0
    left_dict = {}
    left_len = 0

    for a in A:
 
        right_dict[a] -= 1
        right_len -= 1

        if a in left_dict:
            left_dict[a] += 1
        else:
            left_dict[a] = 1
        left_len += 1
        
        if left_dict[a] > left_leader_count:
            left_leader = a
            left_leader_count = left_dict[a]
        
        if left_leader_count > left_len/2 and right_dict[left_leader] > right_len/2:
            count += 1

    return count



  • 제일 처음 처음 전체 값을 오른 쪽 dictionary에 넣어 빈도 수를 만들고 오른쪽 dictionary는 빼고, 왼쪽 dictionary에 추가합니다.

  • 추가하면서, 좌측에서 제일 큰 값을 우측에서도 도출해 내고, 둘다 전체 중에 반을 넘는 지 확인하면, count를 하나씩 늘립니다.

profile
For the sake of someone who studies computer science

0개의 댓글