[프로그래머스] Level2 - 두 큐 합 같게 만들기

1. 문제 설명

Link : https://school.programmers.co.kr/learn/courses/30/lessons/118667

2. 나의 풀이

#include <string>
#include <vector>
#include <numeric>

using namespace std;

typedef unsigned long long ULL;

int solution(vector<int> queue1, vector<int> queue2) 
{
    ULL sum1 = accumulate(queue1.begin(), queue1.end(), 0);
    ULL sum2 = accumulate(queue2.begin(), queue2.end(), 0);

	// 두 수의 합이 홀수인 경우
    if ((sum1 % 2 == 0 && sum2 % 2 == 1) || (sum1 % 2 == 1 && sum2 % 2 == 0))
        return -1;

    int idx1 = 0;
    int idx2 = 0;

    int size = queue1.size();

    int trialCount = 0;

    while (trialCount < size * 2 + size)
    {
        if (sum1 == sum2)
        {
            return trialCount;
        }

        if (sum1 > sum2)
        {
            int pop = queue1[idx1++];
            sum1 -= pop;
            sum2 += pop;

            queue2.push_back(pop);
        }
        else
        {
            int pop = queue2[idx2++];
            sum1 += pop;
            sum2 -= pop;

            queue1.push_back(pop);
        }

        ++trialCount;
    }

    return -1;
}

먼저, 두 큐 총 합을 구해야 한다. 

큐 원소의 최대 크기가 10^9 이고, 최대 300,000개의 원소가 있을 수 있다.

총합은 300,000,000,000,000이 나올 수 있으므로 넉넉한 자료형을 사용하지 않으면 산술 오버플로우가 날 수 있음을 고려해야 한다.

나는 unsigned long long을 사용했다.

 

만약, 두 큐의 총합을 더한 값이 홀수라면, 절대 두 의 원소의 합이 같아질 수 없으니, 예외 처리 해준다.

 

이후에는, 총 합이 더 큰 큐에서 원소 하나를 pop하고, 총합이 작은 큐로 넣어주는 것을 반복한다.

그런데, 반복 조건을 정해주지 않으면 무한루프에 빠질 수 있으므로, 일정 횟수까지만 시도하도록 했다.

 

나의 경우 큐 A의 원소를 큐 B로 모두 옮기고 (A queue size 만큼 try),

큐 B의 원소가 하나 남을 때까지 A로 옮기는 작업 (A queue size + B queue size만큼 try)

을 하고 나면 루프를 끝내는 것으로 설정했다. (문제에서는 두 큐 사이즈가 같으므로 2*size + size)

---

레벨 2로 가니까 난이도가 갑자기 확 뛴 느낌이다...