[C++로 풀이] 쿠키 구입 (투포인터) ⭐⭐⭐⭐

📌 쿠키 구입

난이도 ⭐⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

모든 경우의 “왼쪽 아들이 가진 과자의 합 = 오른쪽 아들이 가진 과자의 합” 중에서 최대값 찾는 문제

• 왼쪽 아들과 오른쪽 아들을 가를 수 있는 기준은 m번 바구니
  • m 번 바구니는 1 번 바구니부터 N - 1 번 바구니까지 될 수 있다. (N 번 바구니가 된다면 오른쪽 아들이 쿠키를 받을 수 없음)
• 현재의 m 번을 기준으로 왼쪽 아들이 받을 수 있는 바구니의 시작점 cookie[m], 오른쪽 아들이 받을 수 있는 바구니의 시작점 cookie[m + 1] 부터 왼쪽 오른쪽 따로 따로 합을 계산해 나간다. 👉 투포인터
• 왼쪽 아들은 m 번을 시작으로 왼쪽으로, 오른쪽 아들은 m + 1 번을 시작으로 오른쪽으로 바구니를 더해나간다.
  • 더 하는 조건
    • 왼쪽 아들이 현재까지 가진 쿠키의 합 > 오른쪽 아들이 현재까지 가진 쿠키의 합
      • 같아져야 하기 때문에 더 작은 오른쪽 아들이 쿠키를 더 가지도록 오른쪽 아들에게 오른쪽 바구니를 가지게 해준다.
    • 왼쪽 아들이 현재까지 가진 쿠키의 합 < 오른쪽 아들이 현재까지 가진 쿠키의 합
      • 같아져야 하기 때문에 더 작은 왼쪽 아들이 쿠키를 더 가지도록 왼쪽 아들에게 왼쪽 바구니를 가지게 해준다.
    • 왼쪽 아들이 현재까지 가진 쿠키의 합 == 오른쪽 아들이 현재까지 가진 쿠키의 합
      • 같은 상태가 되었기 때문에 이렇게 두 아들이 가진 쿠키가 같을 때의 쿠키 개수의 최대값을 저장해둔 answer와 두 아들이 각각 현재까지 가진 쿠키의 수를 비교하고 answer보다 크면 answer에 최대값 업데이트
        • 그리고 마저 비교해나가기 위하여 두 아들이 바구니를 더 가지게 해주어 시작하도록 함.

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> cookie) {
    int answer = 0;
    int N = cookie.size();

    for (int m = 0; m < N - 1; ++m) {
        int left_idx = m;
        int right_idx = m + 1;
        int left_son = cookie[left_idx];
        int right_son = cookie[right_idx];

        while (left_idx >= 0 && right_idx < N) {
            if (left_son < right_son) {
                if (--left_idx >= 0) 
                    left_son += cookie[left_idx];
            }
            else if (left_son > right_son) {
                if (++right_idx < N)
                    right_son += cookie[right_idx];
            }
            else {
                if (answer < left_son)
                    answer = left_son;
                if (--left_idx >= 0)
                    left_son += cookie[left_idx];
                if (++right_idx < N)
                    right_son += cookie[right_idx];
            }
        }
    }
    return answer;
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기