C++:: 프로그래머스 < 두 큐 합 같게 만들기 >

jahlee·2023년 5월 18일
0

프로그래머스_Lv.2

목록 보기
46/106
post-thumbnail

처음에는 굳이 queue를 사용안하고 벡터로 erase를 해가며 큐처럼 활용하였지만 시간초과가 되어서 queue를 활용하여 풀었다.
핵심은 1번 큐를 기준으로 평균값보다 크면 값을 보내고, 작으면 가져온다는 점이다. 언제까지 반복할지에 대한 범위설정도 필요한데 처음에는
answer <= 2*n 이면 될줄알았지만 그것보다 큰 경우가 존재해서 대강 범위를 3*n으로 설정하였다.(최적화를 위한 범위라 생각하면 된다.)

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

int solution(vector<int> queue1, vector<int> queue2)
{
    int answer = 0, n = queue1.size();
    long long sum_all = 0, avg, sum1 = 0;
    queue<int> q1,q2;
    for (int i=0;i<n;i++)
    {
        sum_all += queue1[i];//전체 큐 합
        sum_all += queue2[i];
        sum1 += queue1[i];//1번 큐 합
        q1.push(queue1[i]);
        q2.push(queue2[i]);
    }
    if (sum_all % 2) return -1;// 전체 합이 홀수면
    avg = sum_all/2;
    while (sum1 != avg && answer < 3*n)
    {// 1번 큐가 평균값이 아니거나 동작한 횟수가 3*n보다 작을때
        if (sum1 < avg)
        {// 큐 1의 합이 평균보다 작다면
            sum1 += q2.front();
            q1.push(q2.front()); q2.pop();
        }
        else
        {// 큐 1의 합이 평균보다 크다면
            sum1 -= q1.front();
            q2.push(q1.front()); q1.pop();
        }
        answer++;
    }
    if (answer >= 3*n) return -1;
    return answer;
}

0개의 댓글