(코딜리티) Lesson 10. [Prime and composite numbers] : Flags - python

문제 : app.codility.com/programmers/lessons/10-prime_and_composite_numbers/

10. Prime and composite numbers lesson - Learn to Code - Codility

문제 내용

비어있지 않은 N개의 배열 A가 주어질 때, 0<P<N-1과 A[P-1]<A[P]>A[P+1]를 만족하는 peak를 구하고, 그 peak사이 의 거리가 flag 수 이상 거리가 있어야 한다고 할때, 최대 flag 수를 구하시오.

 

예를 들어, A = [1, 5, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2]일 때,

peak는 아래와 같다.

깃발을 꽂을 수 있는 조건들의 예시는

• 2개일 경우, peak1 과 3에 가능하다.
• 3개일 경우, peak1 과 5와 10에 가능하다.
• 4개일 경우는 peak1과 5와 10 이후로 한개더 부족하기 때문에 3을 return

제한 사항

• N은 1~400,000
• 배열 A의 각 요소는 0~1,000,000,000

코드

import math

def solution(A):
    
    Asize = len(A)
	
    # 배열이 3보다 작은 경우는 peak를 구할 수 없으므로 0 return
    if len(A) < 3:
        return 0
	
	# peak인 index를 담는 list
    peak = []
    for i in range(Asize):
        if  i == 0 or i == Asize-1:
            pass
        elif A[i-1] < A[i] > A[i+1]:
            peak.append(i)
	
    # peak가 2개 이하인 경우는 바로 return
    if len(peak) < 3 :
        return len(peak)
	
    # 제일 처음 peak와 끝 peak 사이에 최대한 깃발을 꽂을 수 있는 갯수
    maxflag = int(math.sqrt(peak[-1]-peak[0]))+1
    
    # 제일처음 peak에서부터 조건을 비교하면서, count로 체크한 후 flag 수(f)를 return
    for f in range(maxflag, 2, -1):
        count = 1
        p = peak[0]
        for i, pe in enumerate(peak):
            if f <= pe-p:
                count += 1
                p = pe
            
        if count >= f:
            break

    return f

해설

peak를 먼저 구하고, 하나씩 돌면서 조건에 만족하는지 안하는지 계산합니다.

이 때, 최대 flag 수 부터 거꾸로 계산을 한다면, 제한시간안에 해결이 가능합니다.

그렇다면, 최대 flag수를 구하는 방법은 아래와 같습니다.

 

"X" : no peak
"P" : yes peak

flag 수에 따라서 최소한으로 요구하는 배열크기는 아래와 같습니다.
1
X P X => 3
2
X P X P X => 5
3
X P XX P XX P X => 9
4
X P XXX P XXX P XXX P X => 15
5
X P XXXX P XXXX P XXXX P XXXX P X => 23
6
X P XXXXX P XXXXX P XXXXX P XXXXX P XXXXX P X => 33


최소 요구 배열크기(minimally required SizeOfArray)를 MRS(N)라고 할 때,
MRS(N) = MRS(N - 1) + (N - 1)*2 (when N > 1), MRS(1) = 3 라는 식이 성립합니다.

MRS(N) = (N - 1)*2 + (N - 2)*2 + (N - 3)*2 + ... + 3*2 + 2*2 + 1*2 + 3 = (N - 1)*(N - 1 + 1) + 3 = (N - 1)*N + 3
∴ MRS(N) = N^2 - N + 3 ≤ N^2 (when N ≥ 3)

대략적으로 MRS(N) = N^2라고 해도 무방합니다.
즉, 3개의 깃발이 필요할 때는, 최소한 배열의 사이즈는 9개 이상이여야 합니다.

반대로 사이즈에 따라서 최대로 가능한 깃발의 수는 
MRS(N)의 역함수를 구하면 됩니다.

∴ MRS^{-1}(N) = N^{1/2} (N의 제곱근)
<example> MRS^{-1}(9) = 3, MRS^{-1}(16) = 4

따라서, 첫번째 peak와 마지막 peak의 차를 구하면 실질적인 배열의 수를 알 수 있고, 
이 배열의 수에 제곱근을 한다면, 최대로 가능한 flat수를 알 수 있습니다.

대략적으로, MRS^{-1}(N) = N^{1/2}에서 +1을 하여 3.8xxx와 같은 값이 나올 때, 3 + 1로 최대 flag수를 지정하고 for문을 돌립니다.
<example> MPN(8) = 3, MPN(9) = 4, MPN(15) = 4, MPN(16) = 5

출처 : github.com/BaeMinCheon/study-101/tree/master/Workspace/2020/06/26

 

이 문제는 풀지 못해서, 여러 솔루션을 찾아봤지만 위와 같이 문제를 접근하고 푸는 것이 제일 간단하고 이해가 쉬운 것 같았습니다. 물론, 저렇게 생각하고 수식은 못세웠을 거 같네요.. 대단합니다...