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

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

Peaks coding task - Learn to Code - Codility

문제 내용

비어있지 않은 N개의 배열 A가 주어질 때, A[P − 1] < A[P] and A[P] > A[P + 1]인 peak를 구하고, peak가 최소한 1개이상 포함된 같은 갯수가 포함된 block을 만들 것이다. 이 때, 최대 block수를 return하시오.

 

예제)

A = [1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2]

이 때, peak의 index는 3, 5, 10이다.

 

조건 대로 block을 나눈다면,

block이 한 개일 때, (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2)가 되고, peak는 3개가 포함된다.

block이 두 개일 때, (1, 2, 3, 4, 3, 4), (1, 2, 3, 4, 6, 2)가 되고, peak는 앞에는 2개, 뒤에는 1개가 포함된다.

block이 세 개일 때, (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2)가 되고, peak는 각 1개씩 포함된다.

block이 네 개일 때는 block안의 요소가 3개인데, (1, 2, 3)인 경우는 peak가 포함되지 않기 때문에 이 때, max block수는 3을 return하면 된다.

제한 사항

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

코드

def solution(A):
    
    Asize = len(A)

    if Asize < 3:
        return 0

    peak = []
    for i in range(1, Asize-1):
        if A[i-1] < A[i] > A[i+1]:
            peak.append(i)

    peak_size = len(peak)
    if peak_size == 0 :
        return 0
    elif peak_size == 1:
        return 1

    for i in range(peak_size, 0, -1):
        if Asize%i == 0:
            count = 0
            block_size = Asize//i
            # block안에 peak가 포함되는 지 알기 위한 list 생성
            block = [0]*i
            for j in range(peak_size):
            	# peak가 몇번째 block에 포함되는 지 판단하기 위함
                idx = peak[j] // block_size
                if block[idx] == 0:
                    block[idx] = 1
                    count += 1
            
            if count == i:
                return i

해설

처음에 짠 코드는 시간초과로 계속 실패해서 구글링 하다가,

            block = [0]*i
            for j in range(peak_size):
                idx = peak[j] // block_size

이 부분을 알게 되어 코드를 바꾼 후 통과하였습니다.

 

block의 갯수를 구한 다음 각 포함하는 요소를 슬라이스 하였는데, (ex. peak[0:4], peak[4:8] ...)

위 부분은 block의 수가 3개라면 [0, 0, 0] 이되고, peak를 하나씩 어디에 포함되는지 계산합니다.

peak 값에 block사이즈의 몫을 구한다면, 위 상황에선 0, 1, 2 중에 하나가 나올 것입니다.

그리고 count를 하면, count와 peak수가 같은 경우 return합니다.