[Codility] Lesson 4: Counting Elements - MaxCounters (javascript)

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/

MaxCounters coding task - Learn to Code - Codility

- 0으로 설정된 N 개의 카운터가 제공
- 카운터는 두 가지 작업이 가능
- increase(X) : 카운터 X가 1씩 증가
- max counter : 모든 카운터의 값이 카운터들 중의 최대 값으로 설정
- N 개의 정수로 이루어진 배열 A가 제공 (비어있지 않음) -> 연속적인 작업을 나타냄
- 1≤X≤N 과 같이 A[K] = X인 경우 K는 increase(X) 작업 수행
- A[K] = N + 1 인 경우 K는 max counter 작업 수행
- 모든 작업이 끝난 후, 모든 카운터의 값을 계산해서 array로 return
- A[N]의 각 element는 [1..N+1]의 정수
- 가장 효율적인 알고리즘으로 작성

 

Solution

CASE 1: 77%

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

function solution(N, A) {
    let counters = new Array(N).fill(0);
    let max = 0;
    
    for(let K in A){
        let X = A[K];
        if(X <= N){
            counters[X-1]++;
            if(max < counters[X-1]){
                max = counters[X-1];
            }
        }
        else{
            counters = new Array(N).fill(max);
        }
        
    }
    
    return counters;
}

- Array.fill을 이용해 초기값 및 max counters 값 세팅
- max 값을 for문 안에서 직접 비교

 

CASE 1: Result

CASE 1의 Result

 

CASE 1: Analysis

CASE 1의 Analysis

 

CASE 2: 66%

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

function solution(N, A) {
    let counters = new Array(N).fill(0);
    
    for(let K in A){
        let X = A[K];
        if(X <= N){
            counters[X-1]++;
        }
        else{
            const max = Math.max.apply(null, counters);
            counters = new Array(N).fill(max);
        }
        
    }
    
    return counters;
}

- Array.fill을 이용해 초기값 및 max counters 값 세팅
- max 값을 Math.max.apply로 비교

 

CASE 2: Result

CASE 2의 Result

 

CASE 2: Analysis

CASE 2의 Analysis

 

CASE 3: 77%

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

function solution(N, A) {
    let counters = [];
    let max = 0;
    
    for(let i=0; i<N; i++){
        counters[i] = 0;
    }
    
    for(let K in A){
        let X = A[K];
        if(X <= N){
            counters[X-1]++;
            if(max < counters[X-1]){
                max = counters[X-1];
            }
        }
        else{
            for(let i=0; i<N; i++){
                counters[i] = max;
            }
        }
        
    }
    
    return counters;
}

- for문을 이용해 counters 값 직접 세팅
- max 값을 for문 안에서 직접 비교

 

CASE 3: Result

CASE 3의 Result

 

CASE 3: Analysis

CASE 3의 Analysis

 

CASE 4: 100%

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

function solution(N, A) {
    let counters = [];
    let max = 0;
    let lastMax = 0;
    
    for(let i=0; i<N; i++){
        counters[i] = 0;
    }
    
    for(let K in A){
        let X = A[K];
        if(X <= N){
            if(counters[X-1] < lastMax){
                counters[X-1] = lastMax;
            }
            counters[X-1]++;
            if(max < counters[X-1]){
                max = counters[X-1];
            }
        }
        else{
            lastMax = max;
        }
        
    }
    
    for(let i=0; i<N; i++){
        if(counters[i] < lastMax){
            counters[i] = lastMax;
        }
    }
    
    return counters;
}

- for문을 이용해 counters 값 직접 세팅
- max : 현재 counters[N] 값들 중의 최대 값
- lastMax : A[K]의 값이 N보다 클 경우(N+1 일 경우)의 max 값
- X : A[K]의 값
- A[K]의 값이 N보다 작거나 같을 경우
    counters의 값이 lastMax보다 작으면 우선 lastMax 값으로 세팅
    increase(X) 수행
    max 값과 비교 후 max값 설정
- A[K]의 값이 N보다 클 경우
    lastMax 값을 현재의 max 값으로 설정
- 다시 한 번 N만큼 for문을 돌면서 lastMax보다 작은 counters 값을 lastMax 값으로 설정

 

CASE 4: Result

CASE 4의 Result

 

CASE 4: Analysis

CASE 4의 Analysis

 

CASE 5: 100%

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

function solution(N, A) {
    let counters = new Array(N).fill(0);
    let max = 0;
    let lastMax = 0;
    
    for(let K in A){
        let X = A[K];
        if(X <= N){
            if(counters[X-1] < lastMax){
                counters[X-1] = lastMax;
            }
            counters[X-1]++;
            if(max < counters[X-1]){
                max = counters[X-1];
            }
        }
        else{
            lastMax = max;
        }
        
    }
    
    for(let i=0; i<N; i++){
        if(counters[i] < lastMax){
            counters[i] = lastMax;
        }
    }
    
    return counters;
}

- Array.fill을 이용해 counters 값 세팅
- max : 현재 counters[N] 값들 중의 최대 값
- lastMax : A[K]의 값이 N보다 클 경우(N+1 일 경우)의 max 값
- X : A[K]의 값
- A[K]의 값이 N보다 작거나 같을 경우
    counters의 값이 lastMax보다 작으면 우선 lastMax 값으로 세팅
    increase(X) 수행
    max 값과 비교 후 max값 설정
- A[K]의 값이 N보다 클 경우
    lastMax 값을 현재의 max 값으로 설정
- 다시 한 번 N만큼 for문을 돌면서 lastMax보다 작은 counters 값을 lastMax 값으로 설정

 

CASE 5: Result

CASE 5의 Result

 

CASE 5: Analysis

CASE 5의 Analysis

 

결론

Math.max.apply는 배열이 큰 경우 비효율적임. (만 건 이상의 element가 있는 배열에서는 사용하지 않는 것이 좋을 듯)

 

배열을 초기화할 때 Array.fill을 사용하는 방법이나 for문을 사용하는 방법은 성능에 크게 차이가 없음. 소스가 훨씬 간단하기 때문에 Array.fill을 사용하는 것이 좋을 듯.