Coding Test] 두 큐 합 같게 만들기 (TP)

[Programmers School 문제 링크]

• Code

#include <string>
#include <vector>

using namespace std;

int answer = -1;

void Sum(vector<int>* v, vector<int>* addV, long long* target, long long* num)
{
    for(auto i : *addV)
    {
        *target += i;
        *num += (long long)i;
        v->push_back(i);
    }
}

void TwoPointer(vector<int> v, int l, int r, long long num, long long target)
{
    int count = 0;
    for(; r < v.size();)
    {
        if(num == target)
        {
            if(answer == -1 || answer != -1 && answer > count)
                answer = count;
            break;
        }
        else if(num < target)   num += (long long)v[++r];
        else                    num -= (long long)v[l++];
        count++;
    }
}

int solution(vector<int> queue1, vector<int> queue2) {
    vector<int> v = queue1;
    long long target = 0, n1 = 0, n2 = 0;
    Sum(&v, &queue2, &target, &n2);
    Sum(&v, &queue1, &target, &n1);
    target /= 2;
    
    int size = queue1.size();
    if(n1 < n2)
        TwoPointer({v.begin(), v.end() - size}, 0, size-1, n1, target);
    else
        TwoPointer({v.begin() + size, v.end()}, 0, size-1, n2, target);
    
    return answer;
}

• 개요

- 두 큐 안의 값을 동일하게 만드는 최소 이동(Push, Pop) 횟수 구하기

- Two Pointer를 이용한 문제해결

• 알고리즘 설명

1. vector<int> queue1과 queue2를 연결한(queue1 ~ queue2 ~ queue1) vector v를 만들며 각 queue에 들어있는 값의 합(n1, n2)과 전체 queue에 들어있는 값의 총합(target)의 반을 구함

2. n1과 n2를 비교하여 작은쪽을 기준으로 삼음(해당 큐에서 값 변경)

3. Two Pointer 알고리즘을 사용

- num < target 이면 다른 큐에서 값을 하나 가져옴

- num > target 이면 현재 큐에서 값을 하나 내보냄

- num == target 이면 현재까지의 이동횟수를 answer와 비교 후 값을 저장하고 종료

• 함수 기능 설명

//Vector 연결, target(전체 벡터의 합)과 num(이번 벡터의 합) 계산
void Sum(vector<int>* v, vector<int>* addV, long long* target, long long* num)
{
    for(auto i : *addV)
    {
        *target += i;            //전체 벡터의 합
        *num += (long long)i;    //이번 벡터의 합
        v->push_back(i);         //Vector 연결
    }
}

//Two Pointer 알고리즘
void TwoPointer(vector<int> v, int l, int r, long long num, long long target)
{
    //이동 횟수
    int count = 0;
    //오른쪽 포인터가 범위를 벗어나면 탐색 종료
    for(; r < v.size();)
    {
        //조건 만족 탈출
        if(num == target)
        {
            //answer가 -1이거나 -1보다 클때 answer가 이동 횟수보다 작으면
            if(answer == -1 || answer != -1 && answer > count)
                answer = count;    //갱신
            break;
        }
        //다른 vector에서 값 가져오기
        else if(num < target)   num += (long long)v[++r];
        //현재 vector에서 값 내보내기
        else                    num -= (long long)v[l++];
        //이동 횟수 증가
        count++;
    }
}

//메인 함수
int solution(vector<int> queue1, vector<int> queue2) {
    //v = { queue1 }
    vector<int> v = queue1;
    
    //target값, n1 = queue1의 총합, n2 = queue2의 총합
    long long target = 0, n1 = 0, n2 = 0;
    
    //v = { queue1 ~ queue2 }
    Sum(&v, &queue2, &target, &n2);
    //v = { queue1 ~ queue2 ~ queue1 }
    Sum(&v, &queue1, &target, &n1);
    
    //target 값 = 두 벡터의 총합 / 2
    target /= 2;
    
    int size = queue1.size();
    //값이 작은 큐(vector)부터 시작
    if(n1 < n2)
        //{ queue1 ~ queue2 }
        TwoPointer({v.begin(), v.end() - size}, 0, size-1, n1, target);
    else
        //{ queue2 ~ queue1 }
        TwoPointer({v.begin() + size, v.end()}, 0, size-1, n2, target);
    
    return answer;
}