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

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

모든 경계를 기준으로 양쪽 방향의 순열의 합이 같아지는 경우의 최대 값을 구하는 문제

 

1)  누적합을 얻기 위한 중복 연산을 방지하기 위한 누적합 배열

- 왼쪽을 기준으로 한 누적합 배열과 오른쪽을 기준으로 한 누적합 배열

 

2) 경계값을 기준으로 양쪽을 나누어 양쪽의 합이 같아지거나, 경계를 넘을 때까지 반복

- 더 큰 쪽의 끝부분부터 잘라내면서 비교 (leftIndex, rightIndex를 이용해 빼줌)

 ex) 3 ~ 5 번 인덱스의 합을 얻고 싶다면 left[5] - left[2] 혹은 right[3] - right[6] 로 구할 수 있음

 

3) 누적합 배열 예시

ex) 누적합 배열이 5일때 누적합 배열 안의 값 ( x : 값이 0 )

 

인덱스	0 1 2 3 4 5
left 인덱스 값	x 0 1 2 3 4	왼쪽을 기준으로 각 인덱스까지의 값에 대한 누적 합
right 인덱스 값	0 1 2 3 4 x	오른쪽을 기준으로 각 인덱스까지의 값에 대한 누적 합

 

즉, x-1과 x를 경계로 둔 양쪽의 누적합은 left[x]와 right[x]가 됨

 

 -> 누적합 배열을 이용해 모든 경계를 기준으로 최대 값을 찾음

 

주석 참조

    using System;

    public class Solution
    {
        public int solution(int[] cookie)
        {
            int answer = 0;
            var left = new int[cookie.Length + 1]; // 왼쪽 기준 누적합 배열 (시작은 0)
            var right = new int[cookie.Length + 1]; // 오른쪽 기준 누적합 배열 (끝은 0)

            // 누적합 배열 값 세팅
            for (int i = 1; i <= cookie.Length; i++)
            {
                left[i] = cookie[i - 1] + left[i - 1];
                right[cookie.Length - i] = cookie[cookie.Length - i] + right[cookie.Length - i + 1];
            }

            // 경계에 따라 나올 수 있는 경우의 수를 비교
            for (int i = 1; i < cookie.Length; i++)
            {
                // 경계에서부터 해당 방향으로의 전체 누적합
                int leftTotal = left[i];
                int rightTotal = right[i];
                
                // 각 방향에 따른 잘라낼 범위
                int leftIndex = 0;
                int rightIndex = right.Length - 1;

                while (true)
                {
                    // 경계를 벗어남 (탈출조건)
                    if (leftIndex > i || rightIndex < i)
                        break;
                    
                    // 현재누적합 = 방향전체누적합 - 잘라낼범위누적합
                    int currLeft = leftTotal - left[leftIndex];
                    int currRight = rightTotal - right[rightIndex];

                    // 조건에 맞는 경우를 찾음
                    if (currLeft == currRight)
                    {
                        answer = Math.Max(answer, currLeft);
                        break; // 더 탐색해서 값을 찾아도 더 작을 것
                    }
                    
                    // 더 큰 쪽의 끝을 잘라냄
                    if (currLeft < currRight)
                        rightIndex--;
                    else // currLeft > currRight
                        leftIndex++;
                }
            }

            return answer;
        }
    }