[Algorithm] Programmers :: 두 큐 합 같게 만들기

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

프로그래머스

 

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
 
    long long target = 0;
    long long queueSum1 = 0;
    long long queueSum2 = 0;
 
    queue<long long> q1;
    queue<long long> q2;
    int maxCount = queue1.size() * 2 + 1;
 
    for (int i = 0; i < queue1.size(); ++i)
    {
        queueSum1 += queue1[i];
        queueSum2 += queue2[i];
 
        q1.push(queue1[i]);
        q2.push(queue2[i]);
    }
 
    target = (queueSum1 + queueSum2) / 2;
 
    while (1)
    {
        if (queueSum1 == queueSum2 && queueSum2 == target)
        {
            break;
        }
 
        else if (answer > maxCount)
        {
            return -1;
        }
 
        if (queueSum1 < queueSum2)
        {
            int temp = q2.front();
            q2.pop();
            q1.push(temp);
            queueSum1 += temp;
            queueSum2 -= temp;
        }
        else 
        {
            int temp = q1.front();
            q1.pop();
            q2.push(temp);
            queueSum1 -= temp;
            queueSum2 += temp;
        }
 
        ++answer;
 
    }
 
    return answer;
}
 

 

처음 주어지는 두 큐의 합의 평균을 target으로 잡은 후, 두 큐의 원소의 합이 각각 target이 될 때까지 pop하고 insert를 한다. 이 때 최소의 횟수를 구하는 문제다.

 

문제에선 큐 어쩌고 저쩌고 했지만 사실 보자마자 투포인터형식인걸 감으로 알긴 했다.

근데 일단 당장은 큐로 옮긴다음 푸는게 바로 풀릴것 같아서 큐로 옮긴다음 풀었다.

 

현재 큐1의 합이 큐2보다 작을 경우, 큐2의 원소를 pop해서 큐1에 push하는 식으로 밸런스를 맞추면서 카운팅하고, 조건이 되면 카운팅한 값을 리턴 시키게했다.

최대카운팅제한조건을 단순히 큐사이트 * 2로 했다가 테스트케이스 2개가 통과 안되길래 다른사람 풀이를 보니 *4로 했더니 통과했다. 그런데 혹시나해서 * 4대신 * 2 +1로 바꿨더니 잘 통과한다.

 

다만 투포인터로 접근하는게 출제자의 의도가 아닌가..하는 생각이 들어서 투포인터로도 풀어봤다.

 

#include <numeric>
 
using namespace std;
 
int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
 
    long long target = 0;
    long long queueSum1 = accumulate(queue1.begin(), queue1.end(), 0ll);
    long long queueSum2 = accumulate(queue2.begin(), queue2.end(), 0ll);
    
    vector<int> q = queue1;
 
    for (int i = 0; i < queue2.size(); ++i)
    {
        q.push_back(queue2[i]);
    }
 
    int maxCount = q.size() + 1;
    int queueSize = q.size();
 
    target = (queueSum1 + queueSum2) / 2;
    
    int q1p_s = 0;
    int q1p_e = queue1.size() - 1;
    int q2p_s = queue1.size();
    int q2p_e = queue1.size() * 2 - 1;
    
    while (1) 
    {
        if (queueSum1 == queueSum2 && queueSum2 == target)
        {
            break;
        }
        else if (answer > maxCount)
        {
            return -1;
        }
 
        if (queueSum1 < queueSum2)
        {
            queueSum1 += q[q2p_s];
            queueSum2 -= q[q2p_s];
 
            ++q2p_s;
            if (q2p_s == queueSize)
            {
                q2p_s = 0;
            }
            
            ++q1p_e;
            if (q1p_e == queueSize)
            {
                q1p_e = 0;
            }
        }
        else
        {
            queueSum1 -= q[q1p_s];
            queueSum2 += q[q1p_s];
 
            ++q2p_e;
            if (q2p_e == queueSize)
            {
                q2p_e = 0;
            }
 
            ++q1p_s;
            if (q1p_s == queueSize)
            {
                q1p_s = 0;
            }
        }
 
        ++answer;
    }
    
    return answer;
}