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

Lv 4. 쿠키 구입

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

---

접근법

문제 접근 알고리즘: 투포인터, 누적합(슬라이딩 윈도우 변형)

문제의 본질

• 연속된 두 구간의 합이 같은 경우 중, 그 합의 최대값 찾기

전략은 간단했다.

• 경계점 m을 기준으로 좌, 우를 투 포인터로 확장

이유는 과자 수는 음수가 없으므로, 합이 작은 쪽을 늘리는 방식이 항상 올바르게 수렴하기 때문이다.

---

풀이 전략은 평범한 투포인터 문제와 같다.

경계점 m을 왼쪽 구간의 끝으로 고정

• 초기 상태

  • 왼쪽 포인터 l = m
  • 오른쪽 포인터 r = m+1
  • left_sum = cookie[l]
  • right_sum = cookie[r]

• 포인터 이동 규칙

  • left_sum == right_sum
    • 최댓값 비교를 통해 정답 갱신
    • 왼쪽, 오른쪽 확장
  • left_sum < right_sum, left_sum > right_sum
    • 값이 작은 쪽 확장

• 종료 조건

  • 포인터가 배열 범위를 벗어나면 종료

---

정답 풀이 코드

풀이

def solution(cookie):
    n = len(cookie)
    answer = 0
    
    for m in range(n-1):
        l = m
        r = m+1
        
        left_sum = cookie[l]
        right_sum = cookie[r]
        
        while True:
            if left_sum == right_sum:
                answer = max(answer, left_sum)
                
                # 양 쪽 모두 확장
                l -= 1
                r += 1
                if l < 0 or r >= n:
                    break
                left_sum += cookie[l]
                right_sum += cookie[r]
            
            elif left_sum < right_sum:
                # 왼쪽 확장
                l -= 1
                if l < 0:
                    break
                left_sum += cookie[l]
            else:
                # 오른쪽 확장
                r += 1
                if r >= n:
                    break
                right_sum += cookie[r]
                
    return answer