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

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기

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