[프로그래머스] Lv.4 쿠키 구입 (Python)

🔎문제

✔️ Summer/Winter Coding(~2018)

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

프로그래머스

 

💡풀이 1

투포인터로 풀었다.

m을 고정하고 왼쪽, 오른쪽을 투포인터로 설정한다.

왼쪽의 합이 오른쪽의 합보다 더 작으면 왼쪽 포인터를 감소시켜 왼쪽의 합을 늘린다.

오른쪽의 합이 왼쪽의 합보다 더 작으면 오른쪽 포인터를 증가시켜 오른쪽의 합을 늘린다.

왼쪽이나 오른쪽중 범위를 초과할경우 while문을 종료하고, 다음 m으로 같은 작업을 반복한다.

 

📃소스코드 1

def solution(cookie):
       
    res = 0
    n = len(cookie)
    
    # m을 고정시킨뒤, l, r을 정한다.
    for m in range(n - 1):
        l, r = m, m + 1
        first, second = cookie[l], cookie[r]
        while True:
            if first == second:
                res = max(res, max(first, second))
            
            if l > 0 and first <= second:
                l -= 1
                first += cookie[l]
            elif r < n - 1 and first > second:
                r += 1
                second += cookie[r]
            else: # 범위초과
                break
    return res

 

💡풀이 2

다풀고 나서 다른사람 풀이를 보던 중 충격적이라.. 블로그에 기록해본다.

itertools의 accumulate을 이용한 풀이다.

오랜만에 파이썬으로 풀이해 잊고있었는데 역시 파이썬은 엄청나다..

 

 accummulate 로 양쪽의 누적합을 구한다.

첫번째 누적합은 reverse 시켜 m, m+1에서 출발한 누적합을 동일하게 나열한다.

누적합의 교집합을 구한다.

최대를 갱신한다.

 

📃소스코드 2

from itertools import accumulate

def solution(cookie):

    res, n = 0, len(cookie)

    for m in range(len(cookie)):
        a = set(accumulate(reversed(cookie[:m + 1])))
        b = set(accumulate(cookie[m + 1:]))
        c = a & b
        
        if c:
            res = max(*c, res)
    
    return res