🔗 링크

코딩테스트 연습 - 쿠키 구입

🍪 문제

쿠키의 갯수가 들어있는 배열 cookie가 주어졌을 때,

l ~ m번까지의 쿠키의 총합과 m+1 ~ r번까지의 쿠키의 총합이 같은 경우 중 가장 큰 경우를 구해야한다.

(1 <= l <= m, m+1 <= r <= N)

👀 예제로 문제 파악하기

입력 : cookie [1, 1, 2, 3]

⇒ 2(1개), 3번(2개) / 4번 바구니(3개)로 나누면 각각 3으로 나눌 수 있다.

입력 : cookie [1, 2, 4, 5]

⇒ 나눌 수 있는 방법이 없으니 0을 리턴한다.

입력 : cookie [0, 3, 3, 3, 3, 3, 5, 5, 5, 6]

⇒ 2~6번(3개씩) / 7~9번(5개씩)으로 나누면 각각 15로 나눌 수 있다.

🖼️ 알고리즘 풀이 설명

위와 같은 cookie 배열이 주어진다고 가정한다.

for문은 0부터 cookie의 길이 - 1를 돌아준다. 이 때 index의 변수 이름은 i로 정했다.

설명의 편의를 위해 i가 6이라고 생각했을 때

left, leftSum, right, righSum 변수를 각각 선언해준다.

left는 i, right는 i + 1값을 넣어주고,

leftSum는 cookie[i], rightSum은 cookie[i + 1]값을 넣어준다.

left는 i를 기준으로 왼쪽으로, right는 i + 1을 기준으로 오른쪽으로 확장한다.

여기부터 for문 안에서 while문을 돌게 된다.

leftSum과 rightSum을 비교하면 3 < 5이기 때문에,

rightSum이 더 크다. 둘의 쿠키 갯수를 맞추어주어야하기 때문에 leftSum에 값을 더해야한다.

따라서 leftSum에 cookie[—left]값을 더해준다.

그럼 위 그림과 같이 조절이 되게 되는데,

이번에는 leftSum(6) > rightSum(5)이기 때문에 rightSum에 값을 더해야한다.

right는 오른쪽으로 확장하기 때문에 rightSum에 cookie[++right]값을 더해준다.

이런식으로 계속 while문을 돌면서 조절한다.

만약 left 또는 right가 맨 끝에 도달해 더 이상 확장을 할 수 없는 상태라면, break를 해서 반복을 멈춘다.

만약 leftSum값과 rightSum 값이 같고, answer보다 값이 크면

answer에 leftSum(또는 rightSum) 값을 삽입해준다.

반복문(for)이 종료되면 answer을 리턴해준다.

😮 알고리즘 풀이 순서

1. answer을 0으로 초기화해준다.
2. 0부터 cookie.length - 1만큼 for문을 돈다.
   • cookie.length - 1을 하는 이유는 right에 i + 1을 넣기 때문에 배열 범위를 벗어날 수 있기 때문이다.
   1. left에는 i, leftSum에는 cookie[i]를 넣어 초기화해준다.
   2. right는 i + 1, rightSum에는 cookie[i + 1]을 넣어 초기화해준다.
   3. while문을 돌려준다. (조건은 true로 걸어준다.)
      • 만약 두 쿠키의 합이 같으며, answer보다 큰 경우에 answer에 새로 저장해준다.
      • 만약 rightSum이 더 크고, left가 0이 아닌 경우(끝이 아닌 경우) leftSum에 cookie[--left]을 누적해준다.
      • 만역 leftSum이 더 크고, right가 cookie.length - 1이 아닌 경우(끝이 아닌 경우) rightSum에 cookie[++right]을 누적해준다.
      • 세 조건 모두 만족하지 않는 경우에는 더 이상 확장을 할 수 없는 상태이기 때문에 break를 걸어준다.
3. answer을 리턴해준다.
   
   

💻 코드

public class Solution {
  public int solution(int[] cookie) {
    int answer = 0;

    for (int i = 0; i < cookie.length - 1; i++) {
      int left = i;
      int leftSum = cookie[i];

      int right = i + 1;
      int rightSum = cookie[i + 1];

      while (true) {
        if (leftSum == rightSum && answer < leftSum) { // 두 형제의 쿠키의 합이 같으며, 쿠키의 합이 기존 answer에 저장했던 값보다 큰 경우
          answer = leftSum; // answer에 새로 저장
        } else if (leftSum <= rightSum && left != 0) { // 오른쪽이 더 많은 경우, 왼쪽을 늘려야함
          leftSum +=  cookie[--left];
        } else if (leftSum > rightSum && right != cookie.length - 1) { // 왼쪽이 더 많은 경우, 오른쪽을 늘려야함
          rightSum +=  cookie[++right];
        } else { // 더 이상 조절할 수 없을 때
          break;
        }
      }
    }

    return answer;
  }

  @Test
  public void 정답() {
    Assert.assertEquals(3, solution(new int[]{1, 1, 2, 3}));
    Assert.assertEquals(0, solution(new int[]{1, 2, 4, 5}));
    Assert.assertEquals(15, solution(new int[]{0, 3, 3, 3, 3, 3, 5, 5, 5, 6}));
  }

}