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

문제 설명

같은 크기의 vector가 두개 주어지고, 두 벡터의 원소들의 합/2 == 벡터1, 벡터2 각 원소들의 합과 같도록 원소를 이동시켜야한다.

벡터1의 원소들의 합과 벡터2의 원소들의 합이 같은지 확인하면 된다.

 

(문제는 queue라고 하는데 인자는 vector 형으로 주어진다.)

 

한 번의 pop과 한 번의 insert 작업은 1회 수행한 것으로 간주한다.

 

제한 사항

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
• 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

입출력 예

queue1	queue2	result
[3, 2, 7, 2]	[4, 6, 5, 1]	2
[1, 2, 1, 2]	[1, 10, 1, 2]	7
[1, 1]	[1, 5]	-1

풀이

(queue1 원소 합 +  queue2 원소 합 ) / 2 값으로 비교 안해도 된다.

빠른 원소 입출력을 위해 vector 원소를 queue로 옯겼다.

저장, 삭제가 빈번히 일어나는 경우라면 vector는 효율성이 떨어진다. (erase 사용이 빈번하면 속도 저하)

 

최소 횟수를 구하는 문제이므로, sum1과 sum2 크기에 따라 이동시켜야 하는 저장소를 바꿔서 계산하도록한다.

while문을 사용하면, 예외처리가 빠짐없이 처리되도록 주의해야한다.

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

int solution(vector<int> queue1, vector<int> queue2) {
  int answer = 0;

	long long sum1 = accumulate(queue1.begin(), queue1.end(), 0);
	long long sum2 = accumulate(queue2.begin(), queue2.end(), 0);
    
    //long long sum = (sum1 + sum2) / 2;
    
	queue<int> q1, q2;
    
    for(int i = 0; i < queue1.size(); i++){
        q1.push(queue1[i]);
        q2.push(queue2[i]);
    } 
    
    while(sum1 != sum2){
        
        if( sum1 < sum2 ){
            int n2 = q2.front();
            q1.push(q2.front());
            q2.pop();
            sum1 += n2;
            sum2 -= n2;
        }
        else if(sum1 > sum2){
            int n1 = q1.front();
            q2.push(q1.front());
            q1.pop();
            sum1 -= n1;
            sum2 += n1;
        }
        else if(sum1 == sum2){
            break;
        }
         answer++;
        
        if(q1.empty() || q2.empty())
            return -1;
        
                
        if(answer > int(queue1.size()) * 3)
            return -1;
    }
	return answer;
}

    

    if(answer > int(queue1.size()) * 3)
            return -1;

부분의 예외처리를 * 2로 했을 때는 정확성 테스트1번이 계속 실패했다.

다른 테스트는 모두 통과해서 빠진 예외처리가 없는지 계속 확인했는데 "경우의 수" 때문이었다!

 

이동할 수 있는 최대 count는 같은 크기의 저장소가 2개라

컨테이너 크기의 2배라고 생각했는데 3배였다.

queue1 -> queue2 -> queue1

: queue1의 모든 원소가 queue2로 이동 후 다시 queue1으로 이동 (=초기 값으로 되돌아 온 경우)

이 때는 어떠한 방법으로도 각 큐의 원소의 합이 같지 않으므로 "-1"를 반환하는 예외처리를 추가한다.