[ Codility 코딜리티 ] Lesson 5 MinAvgTwoSlice Python 파이썬 풀이

 

 

 

// 문제 요약

 

주어진 array A에 대해서

평균이 가장 낮은 subarray의

첫번째 index를 return해라

 

// 문제 풀이

 

머리가 많이 아픈 문제다.

답을 한번 알고나면

나올때마다 풀 수 있지만

답을 알기전까지는 결코 풀 수 없다...

 

구글링을 통해서 많은 풀이를 봤는데

다들 비슷비슷하게 푼 것으로 봐서

이게 거의 유일한 풀이가 아닐까 싶다.

 

우선 subarray와 subsequence 부터 알아야한다.

subarray는 기존의 array에서 slicing하여

만드는게 가능하고

subsequence는 기존의 array를 스캔하여

원하는 값만 모아둔 것을 말한다.

 

 

 

그러니까

[ 1, 3, 5, 7, 9 ]에서

[1, 3]이나 [7, 9]는 subarray

[ 1, 5, 9 ]는 subsequence이다.

 

어떻게 생각해도 O(n**2)가 나오고

prefix sum을 써보려고 해도 잘 안되는데

average of subarray 의 특징을 알면

풀 수 있는 문제다.

 

우선 array 전체의 평균을 보자.

array 전체의 평균은 가장 작은 값과

가장 큰 값 사이에 위치한다.

그러니까 가질 수 있는 평균의 최소값은

array의 가장 작은 값과 같다는 이야기다.

그러면 이 array를 2개의 subarray로 나눠서

각각의 평균을 측정하면 얼마일까

 

연역적인 방법을 통해서 검증해보자.

 

 

이런식으로 2가지 경우,

그러니까 전체 array의 평균이

두 subarray의 평균의 큰 값 보다 클 수 있는가?

두 subarray의 평균의 작은 값 보다 작을 수 있는가?

를 검증해보면

두 subarray의 큰 값보다 클 수 없고

작은 값보다 작을 수 없음을 알 수 있다.

 

 

더 나아가서는

전체 array의 평균값은

subarray의 평균값 중 작은 값보다

"같거나 크다" 라는 것을 알 수 있다.

 

따라서

A의 평균은 A의 subarray a의 평균과 같거나 크고

a 의 평균은 a의 subarray a'의 평균과 같거나 크고

a' 의 평균은 a'의 subarray a''의 평균과 같거나 크고

a'' 의 평균은 a''의 subarray a'''의 평균과 같거나 크고

......

 

이런식으로 가장 작은 단위의 subarray가 나타날때까지

계속해서 그 하한선을 낮춰볼 수 있다.

 

그러면 가장 작은 단위의 subarray는

몇개의 원소를 가지고 있을까?

 

 

문제 원본의 일부분으로 P와 Q의 정의에서

가장 작은 subarray는 원소를 2개 가지는 것을 알 수 있다.

그러므로 우리는 더 큰 subarray를 확인할 필요가 없고

길이를 2로가지는 subarray들만을 확인하면 된다.

 

 

 

그런데 여기서 잘 생각해야할 점은

바로 N이 5인 경우이다.

 

뭐 더 많은 경우의 수가 있겠으나

결국 마지막 subarray를 구해야하는 상황에

5가 나온다면 이 array는 P와 Q의 정의에 의해

2와 3으로 나누어지게 된다.

 

따라서 우리는 길이가 2인 경우 말고

3인 경우까지 같이 확인을 해 줘야 한다.

 

자 그럼 코드를 한번 확인해 보자.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import sys

def solution(A):
    # write your code in Python 3.6
    two_index, two_min_avg = 0, sys.maxsize
    for i in range(len(A) - 1):
        avg = (A[i] + A[i + 1]) / 2
        if avg < two_min_avg:
            two_index, two_min_avg = i, avg

    three_index, three_min_avg = 0, sys.maxsize
    for i in range(len(A) - 2):
        avg = (A[i] + A[i + 1] + A[i + 2]) / 3
        if avg < three_min_avg:
            three_index, three_min_avg = i, avg

    if three_min_avg < two_min_avg:
        return three_index
    elif three_min_avg > two_min_avg:
        return two_index
    else:
        return min(two_index, three_index)

O(N**2)은 족히 걸릴 것 같던 문제가

O(N)짜리 for 2번만에 풀리게 된다.

더군다나 지금 와서 보니 for 문을 잘 짰다면

그냥 하나로 만들었어도 될 일이었다.

 

이런 문제들은 사실

미리 한번 만나보지 않는다면 시험을 치를때

갑작스럽게 떠올리기가 매우 힘든 내용들이다.

앞으로도 좋은 문제들을 더 많이 만나봐야겠다.