2022 카카오 테크 인턴십 기출 두 큐 합 같게 만들기 C++

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

프로그래머스

 

처음에 큐로 풀었는데 잘안풀려서 힌트를 조금 봤더니 투포인터로 풀린데서 풀었는데 시간초과가 났었다.

투포인터로 푸는방법은

1. 큐를 이어 붙여서 하나의 벡터에 추가해준다.

2. 한쪽 포인터는 맨앞에, 뒤쪽 포인터는 기존 하나의 큐 크기의 위치에 놓는다.

3. 그러면 앞쪽 큐를 pop한다고 치면 앞쪽 포인터를 뒤로 움직이고,뒤쪽 큐를 pop하면 뒤쪽 포인터를 뒤로 움직여주면 된다. 

처음에 시간초과 났었는데, 한쪽 큐의 총합을 이미 구하고 포인터를 움직이는 동안 그값을 변경해주면 된다. while문안에서 계속 합계구해서 시간초과 난듯..

이걸 투포인터로 생각을 어떻게 처음부터 할수 있을까..

#include <string>
#include <vector>
#include<deque> 
#include<iostream> 

using namespace std;



int solution(vector<int> queue1, vector<int> queue2) {
    int answer=10000000; 
    long long sum=0;
    vector<int>arr;
    for(int i=0;i<queue1.size();i++){
        sum+=queue1[i];
        arr.push_back(queue1[i]);
    }
    for(int i=0;i<queue2.size();i++){
        sum+=queue2[i];
        arr.push_back(queue2[i]);
    }
    if(sum%2!=0)return -1;
    
    sum/=2;
    
    long long start=0;
    long long end=queue1.size()-1;
    long long cnt=0;
    long long tmp=0;
        
   for(int i=start;i<=end;i++){
        tmp+=arr[i];
    }
    while(start<=end && end<arr.size()){
        
        
        if(tmp==sum){
            answer=cnt;break;
        }
        
        if(tmp>sum){
            tmp-=arr[start];
            start++;
            cnt++;
        }
        if(tmp<sum){
            end++;
            tmp+=arr[end];
            cnt++;
        }
        
    }
    
    
    if(answer==10000000)return -1;
    else return answer;
}