Codility Lesson 5 - MinAvgTwoSlice

문제 설명

N개의 정수로 구성된 비어 있지 않은 배열 A가 주어집니다. 0 ≤ P < Q < N이 되는 한 쌍의 정수(P, Q)를 배열 A의 슬라이스라고 합니다(슬라이스에는 적어도 두 개의 요소가 포함되어 있음에 유의하세요). 슬라이스(P, Q)의 평균은 A[P] + A[P + 1]+ … + A[Q]를 슬라이스의 길이로 나눈 값입니다. 정확히 말하면, 평균은 (A[P] + A[P + 1] + … + A[Q]) / (Q - P + 1)과 같습니다.

예를 들어, 배열 A는 다음과 같습니다:

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

에는 다음 예제 슬라이스가 포함되어 있습니다:

• 슬라이스 (1, 2), 평균은 (2 + 2) / 2 = 2입니다;
• 슬라이스 (3, 4), 평균은 (5 + 1) / 2 = 3입니다;
• 슬라이스 (1, 4), 평균은 (2 + 2 + 5 + 1) / 4 = 2.5입니다.

목표는 평균이 최소인 슬라이스의 시작 위치를 찾는 것입니다.

함수를 작성합니다:

function solution(A);

이 함수는 N개의 정수로 구성된 비어 있지 않은 배열 A가 주어졌을 때 최소 평균을 가진 슬라이스의 시작 위치를 반환합니다. 최소 평균을 갖는 슬라이스가 두 개 이상 있는 경우 해당 슬라이스의 가장 작은 시작 위치를 반환해야 합니다.

예를 들어 배열 A가 주어지면 다음과 같습니다:

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

이면 위에서 설명한 대로 함수는 1을 반환해야 합니다.

다음 가정에 대한 효율적인 알고리즘을 작성합니다:

• N은 [2..100,000] 범위 내의 정수입니다;
• 배열 A의 각 요소는 [-10,000..10,000] 범위 내의 정수입니다.

문제 접근

해당 문제에서는 슬라이스에서는 최소 2개 이상이 포함되어야한다이므로, 우리가 비교하는 부분은 슬라이스의 길이가 2 또는 3 일때만 비교하면된다.

• 왜?! 길이가 4 인 경우는 2개 + 2개 로 분할 할 수 있다. 이렇게 된다면 무조건 길이가 2인 경우보다 크다는것을 의미한다.
• 그래서 4개이상 길이는 비교 대상을 제외하고 길이가 2개 또는 3개로만 비교한다.

1. Index 0, 1 일때 먼저 계산한다.

   1. 왜?! 나중에 반복문으로 순회할때 index 를 2 부터 시작하기때문
   2. index 를 2 부터 시작하는 이유 : slice 길이가 3 개가 가능한 시점이기 때문
2. 해당 반복문을 순회하면서 길이가 2 그리고 길이가 3 인 경우를 비교하여 최솟값을 찾는다.
3. 해당 최솟값이 되는 슬라이스에 시작 index 를 반환한다.

function solution(A) {
  let minAvg = (A[0] + A[1]) / 2
  let minIndex = 0

  for (let i = 2; i < A.length; i++) {
    const avgWithThree = (A[i - 2] + A[i - 1] + A[i]) / 3
    if (minAvg > avgWithThree) {
      minAvg = avgWithThree
      minIndex = i - 2
    }

    const avgWithTwo = (A[i - 1] + A[i]) / 2
    if (minAvg > avgWithTwo) {
      minAvg = avgWithTwo
      minIndex = i - 1
    }
  }

  return minIndex
}