[Codility] Lesson 5: Prefix Sums - MinAvgTwoSlice (javascript) 문제 풀이

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

Task description

원본 사이트 : https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/

MinAvgTwoSlice coding task - Learn to Code - Codility

- N 개의 정수로 구성된 비어 있지 않은 배열 A
- 0≤P<Q<N인 한 쌍의 정수 (P, Q)
- (P, Q) slice의 평균 : (A[P] + A[P+1] + ... + A[Q]) / (Q - P + 1)
- 평균이 최소인 slice의 시작 위치(P)를 return
- 평균이 동일할 경우, 가장 작은 시작 위치(P)를 return
- 가장 효율적인 알고리즘 작성
- N은 [2..100,000] 범위의 정수
- 배열 A의 각 요소는 [-10,000..10,000] 범위의 정수

 

 

Solution

CASE 1: 이차원 배열로 slice의 합계를 이용한 계산 - 60%

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = A.length;
    let sum = Array.from(Array(N+1), () => Array());
    let minAvg = Number.MAX_SAFE_INTEGER;
    let minIndex = 0;
    let avg = 0;

    for(let i=1; i<=N; i++){
        for(let j=0; j<=N-i; j++){
            if(i == 1){
                sum[i][j] = A[j];
            }
            else{
                sum[i][j] = sum[i-1][j] + A[i+j-1];
            }
        }
    }

    for(let i=2; i<=N; i++){
        let minSum = Number.MAX_SAFE_INTEGER;
        let index = 0;
        for(let j=0; j<=N-i; j++){
            if(sum[i][j] < minSum){
                minSum = sum[i][j];
                index = j;
            }
        }
        avg = minSum / i;
        if(avg < minAvg){
            minAvg = avg;
            minIndex = index;
        }
        else if(avg == minAvg){
            if(index < minIndex){
                minIndex = index;
            }
        }
    }

    return minIndex;

}

- sum : slice의 합계를 저장하기 위한 배열
      i : slice에 포함된 배열 요소의 개수
      j : slice의 시작위치(P)
- minAvg : 최소 평균 값
- minIndex : 최소 평균 값일 때의 P값
- slice에 포함된 배열 요소의 개수 별로 최솟값을 구해 해당 개수의 최소 평균 값을 계산하고, 개수 별로 계산한 최소 평균 값을 비교해 최종 최소 인덱스 값을 return

 

CASE 1: Result

 

CASE 1: Analysis

The following issues have been detected: timeout errors.
다음과 같은 문제가 감지되었습니다. 시간 초과 오류.

=> 정확성은 일치하지만 효율성 측면에서 오류 발생

 

CASE 2: 수학적 특성 이용 - 100%

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = A.length;
    let minAvg = (A[0] + A[1]) / 2;
    let minIndex = 0;
    let avg = 0;

    for(let i=2; i<N; i++){
        avg = (A[i-2] + A[i-1] + A[i]) / 3;
        if(avg < minAvg){
            minAvg = avg;
            minIndex = i-2;
        }

        avg = (A[i-1] + A[i]) / 2;
        if(avg < minAvg){
            minAvg = avg;
            minIndex = i-1;
        }
    }

    return minIndex;

}

- a < b인 경우, (a + b)의 평균은 a보다 큼
  (a + b) < (c + d)인 경우, (a + b + c + d)의 평균은 (a + b)보다 큼
- A[P] + ... + A[Q]의 평균 중 최소 평균을 구하는 것이므로 순서가 고정되어 있으므로 그룹으로 나눌 수 있음
- P<Q이기 때문에 한 개인 그룹의 경우는 고려하지 않아도 됨
- 두 개인 경우와 세 개인 경우의 그룹만 비교하면 나머지 경우는 두 그룹을 조합해서 만들 수 있음

 

CASE 2: Result

 

CASE 2: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

결론

이건 진짜 수학적인 개념이 부족하면 풀기 복잡한 문제다.
그래서 나도 결국 구글링을 통해 솔루션을 찾아보고 풀었다.

처음엔 평균을 구하는 항목의 개수가 동일하면 합이 적은 그룹이 평균도 적을테니 그 특징을 이용해서 구하려고 했는데 오히려 그냥 단순하게 평균을 구해서 비교하는 것보다 더 복잡한 코드가 된 것 같다.
여기에서의 주된 개념은 'a < b인 경우, (a + b)의 평균은 a보다 크다'라는 것인데, 이게 생각보다 쉽게 잘 떠오르질 않는 것 같다.

결국은 이런 문제들을 계속해서 풀어보면서 방식을 익히는 것이 도움이 될 것 같다.