Level 4. 쿠키 구입
문제출처: https://programmers.co.kr/learn/courses/30/lessons/49995
코딩테스트 연습 - 쿠키 구입 | 프로그래머스
과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다. 철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 l번 바구니부터 m번 바구니까지, 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다. 단, 두 아들이 받을 과자 수는 같아야 합니다(1 <= l <= m, m+1 <= r <= N). 즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[
programmers.co.kr
중간 지점을 정한 후 왼쪽과 오른쪽으로 두 인덱스를 갖고 과자의 수를 더해가며 조건을 만족할 때의 쿠키의 수가 최대인지 검사해 주었다.
class Solution {
public int solution(int[] cookie) {
int max = 0;
int len = cookie.length;
if (len == 1) {
return 0;
} else if (len == 2) {
return cookie[0] == cookie[1] ? cookie[0] : 0;
}
for (int i = 0; i < len - 1; i++) {
int leftIdx = i;
int rightIdx = i + 1;
int leftSum = cookie[leftIdx];
int rightSum = cookie[rightIdx];
if (leftSum == rightSum) {
max = Math.max(leftSum, max);
}
while(true) {
if (leftSum < rightSum) {
if (leftIdx == 0)
break;
leftIdx--;
leftSum += cookie[leftIdx];
} else if (leftSum > rightSum) {
if (rightIdx == len - 1)
break;
rightIdx++;
rightSum += cookie[rightIdx];
} else {
max = Math.max(leftSum, max);
if (leftIdx == 0 || rightIdx == len - 1)
break;
leftIdx--;
rightIdx++;
leftSum += cookie[leftIdx];
rightSum += cookie[rightIdx];
}
}
}
return max;
}
}
다른 사람의 풀이를 보며 더 좋은 방법을 찾아 기록한다.
바구니에 들은 쿠키의 수의 누적하여 갖고있는 배열을 이용한 방법이다.
길이가 cookie.length + 1, sum[i]은 1 ~ i번 까지의 쿠키의 합을 갖고있는 배열을 만든다.
l과 r에 대해 중간 나누는 지점 mid를 정하면 쿠키의 합은 sum[mid] - sum[l - 1]과 sum[r] - sum[m]으로 구할 수 있다.
위의 방법과 달리 cookie배열을 다시 찾을 필요가 없기 때문에 더 빠르고 mid를 정하는 방법에 이분탐색을 사용하여 검사 횟수를 크게 줄여 냈었다.
public int find(int start, int end) {
int i = start, j = end;
while(start < end) {
int mid = (start + end) / 2;
int s1 = pSum[mid] - pSum[i - 1], s2 = pSum[j] - pSum[mid];
if(s1 == s2) {
return s1;
}else if(s1 < s2) {
start = mid + 1;
}else {
end = mid;
}
}
return 0;
}