두 큐 합 같게 만들기 [Lv. 2]

프로그래머스

두 큐의 합을 같게 만드는 문제입니다.

두 큐의 합이 같아질 때 까지 서로의 데이터를 주고 받고,  주고 받는 횟수를 반환해야 합니다.

 

풀이 방법

간단하게 접근해서 풀면 될것 같습니다.

queue A의 합이 queue B의 합 보다 크다면 A의 데이터를 B로 보내고

B가 더 크다면 B의 데이터를 A로 보내는 걸 반복하는 방식으로 풀면 될 것 같습니다.

 

int answer = 0;

long total_q1 = 0, total_q2 = 0;
int front_q1 = 0, front_q2 = 0;

실제 queue를 사용하지는 않을거기 때문에 front idx를 따로 저장했습니다.

 

for_each(queue1.begin(), queue1.end(), [&total_q1](int val) {total_q1 += val;});
for_each(queue2.begin(), queue2.end(), [&total_q2](int val) {total_q2 += val;});

for_each문을 이용해서 total 값을 구했습니다.

 

int cnt = queue1.size() + queue2.size() + 10; 
while (total_q1 != total_q2 && cnt--)
{
    if (total_q1 > total_q2)
    {
        int value = queue1[front_q1];
        total_q1 -= value;
        total_q2 += value;
        queue2.push_back(value);

        ++front_q1;

    }
    else
    { 
        int value = queue2[front_q2];
        total_q2 -= value;
        total_q1 += value;
        queue1.push_back(value);

        ++front_q2;
    }
    answer++;
}

영원히 종료되지 않는 경우도 있기에 최대 반복 횟수를 정해주었습니다.

반복하는 최대 횟수(cnt)는 두 수의 합 + 10(대충 여유있게) 으로 했습니다.

total이 큰 queue에서 작은 queue로 데이터를 옮기는 것을 반복했습니다.

 

if(total_q1 != total_q2)
    return -1;

return answer;

while문이 종료되었는데 두 합이 다르다면 -1을 반환, 아니면 answer을 반환