프로그래머스 쿠키 구입 (C++, C#)

프로그래머스

각 바구니 안에 든 과자의 수를 배열로 입력 받을 때, 첫째 아들에게는 i번 바구니부터 m번 바구니 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지 주려고 합니다. 단, 두 아들이 받을 과자의 수는 같아야합니다.

조건에 맞게 과자를 구매할 때, 한 명의 아들에게 가장 많이 줄 수 있는 과자의 수를 찾아주세요.

 

 

풀이 방법

투포인터 알고리즘을 이용하여 풀이합니다. 

L과 R을 비교하여 L이 더 작다면 L의 범위를 더 늘려주고,

R이 더 작다면 R의 범위를 늘려주는 방식으로 해결합니다.

L과 R의 시작 지점이 되는 곳은 여러개이기 때문에 반복문을 통해 해결합니다.

 

for (int i = 0; i < cookie.Length-1; i++)
{
    int l = i;
    int r = l+1;
    
    int lsum = cookie[l];
    int rsum = cookie[r];

 

기준점이 될 l과 r의 시작 위치를 반복문을 통해 결정합니다.

 

while(true)
{
    if (lsum == rsum)
        answer = Math.Max(answer, lsum);

    if (l > 0 && lsum <= rsum)
        lsum += cookie[--l];

    else if (r < cookie.Length-1 && rsum <= lsum)
        rsum += cookie[++r];

    else
        break;
}

while문 안에서 포인터를 조작합니다.

lsum이 rsum보다 작다면 lsum의 크기를 rsum과 맞추기 위해 l에 -1을 더해주어 lsum의 범위를 늘려줍니다.

rsum이 더 작은 경우에는 반대로 진행합니다.

만약 두 크기가 같다면 구매할 수 있는 경우의 수를 찾은 것 이기 때문에 answer을 업데이트 해줍니다.

 

정답 코드 C#

using System;

public class Solution {
    public int solution(int[] cookie) {
        int answer = 0;
        
        for (int i = 0; i < cookie.Length-1; i++)
        {
            int l = i;
            int r = l+1;
            
            int lsum = cookie[l];
            int rsum = cookie[r];
            
            while(true)
            {
                if (lsum == rsum)
                    answer = Math.Max(answer, lsum);
                
                if (l > 0 && lsum <= rsum)
                    lsum += cookie[--l];
                
                else if (r < cookie.Length-1 && rsum <= lsum)
                    rsum += cookie[++r];
                
                else
                    break;
            }
        }
        return answer;
    }
}

 

 

정답 코드 C++ 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> cookie) {
    int answer = 0;
    
    for (int i = 0; i < cookie.size()-1; i++)
    {
        int l = i;
        int r = l+1;
        int lsum = cookie[l];
        int rsum = cookie[r];
        
        while (true) 
        {
            if (lsum == rsum) 
                answer = max(lsum, answer);
            
            if (0 < l && lsum <= rsum) 
                lsum += cookie[--l];
            
            else if (r < cookie.size()-1 && lsum >= rsum) 
                rsum += cookie[++r];
            
            else 
                break;
            
        }
    }
    
    return answer;
}