[쿠키 구입/LV4/Python3]

프로그래머스 쿠키 구입 LV4

 

 

 

문제 설명
과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다. 철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 l번 바구니부터 m번 바구니까지, 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다. 단, 두 아들이 받을 과자 수는 같아야 합니다(1 <= l <= m, m+1 <= r <= N). 즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[l]+..+A[m] = A[m+1]+..+A[r] 를 만족해야 합니다. 각 바구니 안에 들은 과자 수가 차례로 들은 배열 cookie가 주어질 때, 조건에 맞게 과자를 살 경우 한 명의 아들에게 줄 수 있는 가장 많은 과자 수를 return 하는 solution 함수를 완성해주세요. (단, 조건에 맞게 과자를 구매할 수 없다면 0을 return 합니다)

제한사항
cookie의 길이는 1 이상 2,000 이하입니다.
cookie의 각각의 원소는 1 이상 500 이하인 자연수입니다.

 

 

 

누적합을 통해 특정 지점까지의 바구니에 속한 쿠키 개수의 합을 구할 수 있다.

 

m번 바구니를 먼저 정해두고, 해당 바구니를 기준으로 조건에 맞는 과자 수를 찾도록 l과 r을 늘리는 방식을 사용했다.

l과 r을 정해두고 조건에 가장 가까운 m번 바구니를 이분 탐색으로 찾는 방식으로는 효율성에서 시간 초과에 걸려 통과하지 못 했다.  O(n^2 * log N)

 

m번 바구니를 미리 정하면, 모든 원소를 원소 개수만큼 확인하기 때문에 O(n^2) 시간복잡도로 답을 구할 수 있다.

 

 

def solution(cookie):
    sums = [0] * len(cookie)
    for i in range(len(cookie)):
        sums[i] = cookie[i] + sums[i-1]
    
    max_sum = 0
    
    def find(m):
        s, e = m, m+1
        max_val = 0
        while s>=0 and e<len(cookie):
            s_to_m = sums[m] - sums[s] + cookie[s]
            m_to_e = sums[e] - sums[m]
            if s_to_m == m_to_e:
                max_val = max(max_val, m_to_e)
            if s_to_m < m_to_e:
                s -=1
            else:
                e += 1
        return max_val
        
    for i in range(len(cookie)-1):
        max_sum = max(find(i), max_sum)
    
    return max_sum

 

---