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

풀이 소요시간 : 풀이 참고(실패)

접근하지 못한 핵심 포인트는 다음과 같다.

1. 작은 큐 에서 큰 큐로 원소를 넘겨주는 행위의 반복이 최적 값이다.
2. 원소 이동의 최대치는 전체 원소 * 2 이다.

1번 포인트를 생각하지 못한 이유는 너무 단순해서 저런 것이 최적 값일 거라는 생각을 못했다는 것이다. 구간 합을 구해가며 최적 값을 찾아야 하는줄 알고 많은 시간을 소모했다.

2번 포인트를 생각하지 못한 이유는 머리가 나빠서 + 1번 포인트에 접근하지 못해서다. 메모장에 예시 과정을 적어보고 나서야 알게되었는데, 1번 규칙에 따라 전체 원소 * 2 회의 이동을 반복하면 큐가 원상 복구된다.

후에 알게된 것은 그냥 큐 를 사용하여 구현해도 위의 포인트를 알고있다면 투 포인터 를 사용하지 않고도 통과가 되는 문제였다.

전체 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    
    long long sum1 = 0, sum2 = 0;
    
    vector<int> Vector;
    for(int e : queue1) 
    {
        Vector.push_back(e);
        sum1 += e;
    }
    for(int e : queue2) 
    {
        Vector.push_back(e);
        sum2 += e;
    }
    
    int s1 = 0;
    int e1 = queue1.size() - 1;
    int s2 = queue1.size();
    int e2 = queue1.size() * 2 - 1;
    
    int ans = 0;
    int N = Vector.size();
    
    while(ans < N * 2)
    {
        if(sum2 < sum1)
        {
            sum1 -= Vector[(s1++) % N];
            //q1 에서 첫 원소를 pop
            
            sum2 += Vector[(++e2) % N];
            //q2 에 q1 의 첫 원소를 push
        }
        else if(sum2 > sum1)
        {
            sum2 -= Vector[(s2++) % N];
            //q2 에서 첫 원소를 pop
            
            sum1 += Vector[(++e1) % N];
            //q1 에 q2 의 첫 원소를 push
        }
        else return ans;
        
        ans++;
    }
    
    return -1;
    
}