[프로그래머스] 쿠키 구입

https://school.programmers.co.kr/learn/courses/30/lessons/49995

프로그래머스

🤔 문제분석

연속된 배열이 주어졌을때, A[l] + … A[m] = A[m+1] + .. + A[r] 을 만족하는 A[i] + .. A[m]의 최대값을 구해야한다.

주어진 배열의 크기가 2000 이하이니 N의 제곱으로 문제를 접근하였습니다. 모든 경우의수를 다 탐색해보고 가장 최대값을 갱신하면되는데 두 가지의 조건으로 이중 반복문을 구성하여 문제를 해결 하였습니다.

1. i번째 인덱스로부터 배열을 나눈다.
2. 투포인터를 활용하여 각각의 나눈 배열을 좌측 혹은 우측으로 땡겨보면서 값을 비교해 나아간다.

💻 코드

def solution(cookie):
    if len(cookie) == 1:
        return 0

    answer = 0
    for i in range(1, len(cookie)):
        l_p = 0
        r_p = len(cookie)
        l_sum = sum(cookie[l_p:i])
        r_sum = sum(cookie[i:r_p + 1])
        while r_p > l_p:
            if l_sum == r_sum:
                answer = max(answer,l_sum)
                break
            elif l_sum > r_sum:
                l_sum -= cookie[l_p]
                l_p += 1
            else:
                r_sum -= cookie[r_p-1]
                r_p -= 1

    return answer

🎯 피드백 및 개선사항

다른사람의 풀이를 참조해보았는데요, accumulate 함수를 써서 문제를 해결한것이 흥미로워 아래와 같이 공유합니다.

모든 경우의 수를 accumlate 함수를 통하여 구한뒤 set() 에 넣었습니다. set()에 넣은뒤 비트 연산을 통하여 값이 같은 경우를 찾아내고 최대값으로 갱신합니다.

from itertools import accumulate

def solution(cookie):
    answer = 0
    for m in range(len(cookie)-1):
        a = set(accumulate(reversed(cookie[:m+1])))
        b = set(accumulate(cookie[m+1:]))
        c = a & b

        if c:
            answer = max(*c, answer)
    return answer