[Codility/Lesson10]Peaks

| 1트 ~ 대충 많이 시도함

def solution(A):

    length = len(A)
    peak_array = []

    for i, _ in enumerate(A):
        if i - 1 < 0:
            continue
                 
        if i + 1 >= length:
            continue
     
        if A[i-1] < A[i] and A[i+1] < A[i]:
            peak_array.append(i)
    
    peak_length = len(peak_array)

    if peak_length == 0: return 0 
    #print(peak_array)

    for peak in peak_array:
        block_num , possible = divmod(length, peak + 1 )
        if possible != 0:
            continue
        count = 0 
        #print(block_num, possible)
        for block in range(block_num):
            if peak_length > block and block * (peak + 1) <= peak_array[block] <= block * (peak + 1) + peak:
                count += 1 
                if count == block_num:
                    #print("block num ::: " + str(block_num + 1))
                    return block_num
            else:
                break 

    return 1

• block의 크기가 무조건 peak + 1 이여야 하는 줄 알고 위와 같이 짰다
  
• 그런데 위와 같은 반례가 있어서 꼭 peak + 1은 아니여도 되는 것을 알았다
• 물론 최소값은 peak + 1부터 시작해야 한다

결과는 여기에

| 막트

def solution(A):

    length = len(A)
    peak_array = []
    peak_true_array = [0 for _ in range(length)]

    for i, _ in enumerate(A):
        if i - 1 < 0:
            continue
                 
        if i + 1 >= length:
            continue
     
        if A[i-1] < A[i] and A[i+1] < A[i]:
            peak_array.append(i)
            peak_true_array[i] = 1
    
    peak_length = len(peak_array)

    if peak_length == 0: return 0 
    #print(peak_array)
 
    for block_size in range(peak_array[0] + 1, length + 1):
        block_num , possible = divmod(length, block_size)
        if possible != 0:
            continue

        #print(block_num, block_size)
        count = 0
        for idx in range(block_num):
            for i in range(idx * block_size, idx * block_size + block_size):
                if peak_true_array[i] == 1:
                    count += 1 
                    break 
        #print("count ::: " + str(count))
        if count == block_num:
            return block_num

• peak 값을 구한 후 peak + 1 부터 length + 1까지 block 의 크기를 지정했다
• 모든 block 을 탐색해서 block에 peak를 포함하고 있으면 count +=1을 해주었다
• count 가 block의 갯수와 같다면 return 해주도록 했다

결과는 여기에