[Codility/Lesson10]Flags

codility에서는 공식적으로 두가지 방법에 대해 소개하고 있다

| 1트

def solution(A):

    length = len(A)
    peak_array = [0 for _ in range(length)]
    peak_length = 0
    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[i] = 1
            peak_length += 1 

    last_num = 0 
        
    for flags in range(1, peak_length + 1):
        pos = 0
        flag_num = flags
        while flags > 0 and pos < length:
            if peak_array[pos]:
                flags -= 1 
                pos += flag_num
            else:
                pos += 1 
        
        if flags == 0 :
            last_num = flag_num
        else:
            break
    return last_num

• 첫번째 방법으로 진행할 경우 timeout이 발생한다
• flags는 peak의 길이가 최대이기 때문에 peak의 길이만큼 비교를 해주었다

결과는 여기에

| 2트

def solution(A):

    length = len(A)
    peak_array = [0 for _ in range(length)]
    peak_length = 0
    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[i] = 1
            peak_length += 1 
            #print(i)

    next_peak = [0 for _ in range(length)]

    next_peak[-1] = -1
    for i in range(length - 2, -1, -1):
        if peak_array[i] == 1:
            next_peak[i] = i
        else:
            next_peak[i] = next_peak[i+1]

    
    flag = 1 
    result = 0 

    #print(next_peak)

    while (flag - 1) * flag <= length:
        pos = 0 
        num = 0 
        while pos < length and num < flag:
            pos = next_peak[pos]
            #print("pos :: " + str(pos))
            if pos == -1:
                break 
            num += 1 
            pos += flag 
        result = max(result, num)
        flag += 1 
    return result 
    

• 다른건 다 이해 되는데 N/i + 1 >= i 여야 한다는게 계속 이해가 안됐다
• 그래서 다음과 같이 바꾸어서 했는데도 똑같은 결과가 나왔다

결과는 여기에

def solution(A):

    length = len(A)
    peak_array = [0 for _ in range(length)]
    peak_length = 0
    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[i] = 1
            peak_length += 1 
            #print(i)

    next_peak = [0 for _ in range(length)]

    next_peak[-1] = -1
    for i in range(length - 2, -1, -1):
        if peak_array[i] == 1:
            next_peak[i] = i
        else:
            next_peak[i] = next_peak[i+1]

    
    flag = 1 
    result = 0 

    #print(next_peak)

    while flag <= length:
        pos = 0 
        num = 0 
        while pos < length and num < flag:
            pos = next_peak[pos]
            #print("pos :: " + str(pos))
            if pos == -1:
                break 
            num += 1 
            pos += flag 
        result = max(result, num)
        flag += 1 
    return result 
    

• 다른건 다 똑같이 하고 flag를 length만큼만 돌도록 하게 바꾸었다
• 결국 중요한건 flag를 어디까지 하는가가 아니라 다음 peak를 빠르게 찾아가는 것