[프로그래머스 C++] 두 큐 합 같게 만들기

 

[프로그래머스 C++] 두 큐 합 같게 만들기

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

해결방안

 

큐, Queue

---

 

처음 시도한 코드

 

#include <queue>
#include <vector>
using namespace std;
 
queue<int> Q, calQ;
int sumNum;
int answer;
 
int solution(vector<int> queue1, vector<int> queue2) {
	int n = queue1.size();
	for(int i=0; i<n; i++){
		sumNum += (queue1[i] + queue2[i]);
		Q.push(queue1[i]);
	}
	for(int i=0; i<n; i++){
		Q.push(queue2[i]);
	}
 
	bool success = false;
	int maxTry = 4 * n;
	int total = 0;
	while(!Q.empty() && maxTry--)
	{
		answer++;
        
		if (total > sumNum / 2) 
		{
			total -= calQ.front();
			calQ.pop();
		}
		else if (total < sumNum / 2)
		{
			total += Q.front();
			calQ.push(Q.front());
		}
		else if (total == sumNum / 2)
		{
			success = true;
			break;
		}
 
		int front = Q.front();
		Q.pop();
		Q.push(front);
	}
    
	if (success) answer -= (n-1);
	else answer = -1;
 
    return answer;
}

 

---

 

 

정답코드

 

#include <queue>
#include <vector>
using namespace std;
 
queue<int> Q1, Q2;
long long sum1, sum2, sumNum;
int answer;
 
int solution(vector<int> queue1, vector<int> queue2) {
	int n = queue1.size();
	for(int i=0; i<n; i++){
		sumNum += queue1[i] + queue2[i];
		sum1 += queue1[i];
		Q1.push(queue1[i]);
		sum2 += queue2[i];
		Q2.push(queue2[i]);
	}
    
	bool success = false;
	int maxTrial = 3 * n;
	while (maxTrial--)
	{
		if(sum1 == sum2){
			success = true;
			break;
		}
		else if(sum1 < sum2){
			sum1 += Q2.front();
			sum2 -= Q2.front();
			Q1.push(Q2.front());
			Q2.pop();
		}
		else{ // sum1 > sum2
			sum1 -= Q1.front();
			sum2 += Q1.front();
			Q2.push(Q1.front());
			Q1.pop();
		}
        
		answer++;
	}
 
	if (false == success) answer = -1;
 
    return answer;
}

 

 

---