과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다.
철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 l번 바구니부터 m번 바구니까지, 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다. 단, 두 아들이 받을 과자 수는 같아야 합니다(1 <= l <= m, m+1 <= r <= N). 즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[l]+..+A[m] = A[m+1]+..+A[r] 를 만족해야 합니다.
각 바구니 안에 들은 과자 수가 차례로 들은 배열 cookie가 주어질 때, 조건에 맞게 과자를 살 경우 한 명의 아들에게 줄 수 있는 가장 많은 과자 수를 return 하는 solution 함수를 완성해주세요. (단, 조건에 맞게 과자를 구매할 수 없다면 0을 return 합니다)
제한사항
- cookie의 길이는 1 이상 2,000 이하입니다.
- cookie의 각각의 원소는 1 이상 500 이하인 자연수입니다.
조건에 맞게 구입을 하려면 이러한 느낌으로 하면 될 것 같다
1. 첫 번째 바구니부터 (마지막 바구니 -1) 까지의 바구니를 첫째 아들에게 줄 수 있다
2. 첫 째 아들에게 사 준 바구니들의 다음 바구니부터 조건을 체크한다
2-1. 과자의 개수가 작을 경우 그 다음 바구니의 개수를 합산하여 다시 조건을 체크
2-2. 과자의 개수가 같을 경우 그 값을 정답으로 저장해둔 뒤 첫 번째 아들의 바구니 구매 수를 늘리고 처음부터 다시 시작
2-3. 과자의 개수가 많을 경우 값을 저장하지 않고 첫 번째 아들의 바구니 구매 수를 늘리고 처음부터 다시 시작
형식으로 첫 번째 아들에게 1번 바구니부터 n-1번의 바구니까지 주는 경우의 수를 쭉 체크해주면 정답을 찾을 수 있다고 예상했다.
using System;
public class Solution {
public int solution(int[] cookie) {
int answer = 0;
int length = cookie.Length;
for(int i = 0; i <= length-2; i++)
{
bool isCorrespond = false; //갯수가 맞을 경우 반환할 bool값
int aSon = cookie[i]; //첫째 아들이 받을 과자의 갯수
int bSon = 0; //둘째 아들이 받을 과자의 갯수
int addCookie = i; //첫째 아들의 바구니 갯수 추가
int maxCookie = 0;
for(int j = i+1; j <= length-1; j++)
{
bSon += cookie[j];
if(aSon == bSon)
{
maxCookie = aSon;
isCorrespond = true;
addCookie++;
aSon += cookie[addCookie];
bSon = 0;
j = addCookie;
}
else if (aSon < bSon)
{
addCookie++;
aSon += cookie[addCookie];
bSon = 0;
j = addCookie;
}
}
if (isCorrespond == true && answer < maxCookie) //bool값이 true이고 리턴할 보다 현재 찾아낸 값이 클 경우
{
answer = maxCookie;
}
}
return answer;
}
}
테스트를 돌려본 결과, 정답은 맞췄으나 시간이 길어져서 효율성에서 통과하지 못했다.
검색을 통해 누적합과 구간합이라는 로직을 알아냈다.
누적합
int[] prefixSum = new int[length + 1];
for (int i = 1; i <= length; i++) {
prefixSum[i] = prefixSum[i - 1] + cookie[i - 1];
}
새로운 배열을 만들어
입력받을 배열만큼의 크기를 만듬
기존 배열이 [1,2,3,4,5] 일 경우
1
1+2 = 3
3+3 = 6
6+4 = 10
10+5 = 15
같이 기존 배열의 값을 하나하나 더하여 새로운 배열에 등록해주는 것을 누적합 알고리즘이라고 한다.
구간합
위에서 구한 누적합에서
2,3 바구니의 합을 구하고 싶다 하면
1~3 바구니의 합에서 1 바구니를 뺴주고,
3,4바구니의 합을 구하고 싶으면
1~4 바구니의 합에서 1~2 바구니의 합을 뺴주는 형식이면 구간합이 구해지는 것이다.
누적합을 배열로 미리 구해놨기 때문에 이 부분의 연산이 매우 빨라진다.
ex) 첫 번째 아들이 2,3 바구니를 받았고, 두 번째 아들이 4,5 번 바구니를 받았을 때
첫 번째 아들의 쿠기 개수 = 1~3바구니의 쿠키 갯수 - 1바구니의 쿠키 갯수
두 번째 아들의 쿠키 개수 = 1~5바구니의 쿠키 갯수 - 1~3바구니의 쿠키 갯수
형식으로 비교하면 값이 비교가 될 것이다.
연산은 첫째 아들의 시작 바구니를 점점 오른쪽으로 옮겨가며
각자의 첫 째 바구니를 비교하고,
첫째 아들의 값이 크다면 둘째 아들의 바구니를 우측으로 확장해주며 쿠키를 합산해주고
둘째 아들의 값이 같거나 크다면 첫째 아들의 바구니를 좌측으로 확장해주며 개수를 늘린다.
using System;
public class Solution {
public int solution(int[] cookie) {
int answer = 0;
int length = cookie.Length;
int[] prefixSum = new int[length + 1]; //누적합을 담을 배열 생성
for (int i = 1; i <= length; i++)
{
prefixSum[i] = prefixSum[i - 1] + cookie[i - 1];
} // 누적합 배열 등록
// i는 첫째 아들의 기준점 i+1은 둘째 아들의 기준점
for (int i = 0; i < length - 1; i++)
{
int left = i, right = i + 1;
// left가 0보다 작거나 rigth가 길이를 넘어가는 순간 종료
while (left >= 0 && right < length)
{
int aSon = prefixSum[i + 1] - prefixSum[left]; // 첫째 아들 구간합
int bSon = prefixSum[right + 1] - prefixSum[i + 1]; // 둘째 아들 구간합
if (aSon == bSon)
{
answer = Math.Max(answer, aSon);
}//값이 같다면 기존 값과 현재 찾은 중 최대값을 골라 입력
if (aSon <= bSon)
{
left--; // 첫째 아들에 구간을 확장
} else {
right++; // 둘째 아들 구간을 확장
}
}
}
return answer;
}
}
수정한 로직을 적용하면 효율성 테스트도 통과할 수 있다.