[Codility] 10.4 Peaks

Peaks 문제 풀기

문제를 간단히 요약하면 다음과 같다

1. 배열 A의 크기는 N이다
2. 0 < P < N - 1에 대하여 A[P - 1] < A[P] and A[P] > A[P + 1]을 만족하면 P에서 peak라고 한다. (극대와 같은 개념)
3. 배열 A를 나누어서 부분배열의 원소가 같게 하려고 한다. 이때 부분배열을 block이라 하자
   3.1 각 block들은 반드시 peak를 포함해야 한다.
   3.2 block의 양 끝에 peak가 있는 것은 peak를 포함하는 것으로 간주한다.
4. 1~3을 만족하는 block중 최대 block의 개수를 구하시오

조건 3을 만족하기 위해서는 block의 개수는 반드시 N의 약수여야 한다. 약수를 판단하기 위해서 $\sqrt{n}$까지만 판단하면 된다.

3.1을 판단하기 위해서 전처리과정을 통해 peak_cnt를 이용한다. peak_cnt[x]는 x까지의 peak의 누적 개수이다. 따라서 peak_cnt[x] - peak_cnt[y - 1]가 양수라면 구간 [y, x]에서 peak를 포함한다는 뜻이다.
3.2를 판단하려면 peak_cnt[x] - peak_cnt[y - 1] == 0이면서 A[y]가 peak이면 된다.

def solution(A):
    isPeak = [False] * len(A)
    for i in range(1, len(A) - 1):
        if A[i] > A[i - 1] and A[i] > A[i + 1]:
            isPeak[i] = True
    
    peak_cnt = [0] * len(A)
    for i in range(1, len(A)):
        peak_cnt[i] = peak_cnt[i - 1]
        if isPeak[i]:
            peak_cnt[i] += 1
    
    N = len(A)
    m = int(N ** 0.5) + 1
    answer = 0
    for i in range(1, m):
        if N % i == 0:
            elems = i
            allHasPeak = True
            for idx in range(elems - 1, N, elems):
                if peak_cnt[idx] == peak_cnt[idx - elems + 1] and not isPeak[idx - elems + 1]:
                    allHasPeak = False
                    break
            if allHasPeak:
                answer = max(answer, N // elems)


            elems = N // i
            allHasPeak = True
            for idx in range(elems - 1, N, elems):
                if peak_cnt[idx] == peak_cnt[idx - elems + 1] and not isPeak[idx - elems + 1]:
                    allHasPeak = False
                    break
            if allHasPeak:
                answer = max(answer, N // elems)
                
    return answer

codility에서 측정한 시간복잡도는 $O(n \log(\log{n}))$이다. 아마 소수판정도 같이 들어있어서 가장 바깥에 있는 반복문을 $O(\log\log{n})$으로 생각한 것 같다.