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

 

문제 

---

 

 

 

 

 

풀이

---

 

문제에도 언급했듯, 총합을 구하고 반 나눈 수가 각 큐 안에 든 수들의 합이 되도록 해야한다. 두 큐에 든 숫자들의 합이 30이면, 각 큐의 합은 각 각 15가 되도록 맞추는 것이다.

 

 

그렇다면 언제 -1이 나오게 되는가? 

 

1. 두 큐의 합이 홀수면 반으로 나눌 수 없으니, 어떻게 해도 두 큐의 합이 같도록 할 수 없다.

 

2. queue 사이즈 만큼의 횟수를 두 번 이상 반복하면, 각 큐에 들어있던 수가 서로 뒤바뀐다. 즉, 그 이상 반복하면 의미가 없다. 

 

 

 

 

    int answer = 0;
    long long sum1 = 0;
    long long sum2 = 0;
    long long sum;
    queue<int> q1;
    queue<int> q2;
    
    for(int i = 0 ; i < queue1.size(); i++){
        sum1 += queue1[i];
        q1.push(queue1[i]);
    }
    
    for(int i = 0 ; i < queue2.size(); i++){
        sum2 += queue2[i];
        q2.push(queue2[i]);
    }

 

큐 두개를 선언해서 각 queue1, queue2의 요소들을 넣었다. 난 처음부터 큐를 썼지만, 큐를 쓰지 않고 벡터를 사용하면 시간 초과가 발생할 수 있다고 한다.

 

 

 

sum1, sum2는 각 각 queue1, queue2에 들어있는 수들의 합이 되겠다.  sum1과 sum2를 계속 비교하면서, 큰 쪽이 작은 쪽의 큐에게 수를 넘겨주는 것이 최적의 해가 될 것이라 생각하고 구현했다.

 

 

코드

---

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    long long sum1 = 0;
    long long sum2 = 0;
    long long sum;
    queue<int> q1;
    queue<int> q2;
    
    for(int i = 0 ; i < queue1.size(); i++){
        sum1 += queue1[i];
        q1.push(queue1[i]);
    }
    
    for(int i = 0 ; i < queue2.size(); i++){
        sum2 += queue2[i];
        q2.push(queue2[i]);
    }
    
    sum = sum1 + sum2;
    
    if(sum % 2 != 0) return -1;
    
    while(answer <= queue1.size() * 3 ){
        if(sum1 == sum2)
            return answer;
        if(q1.empty() || q2.empty())
            return -1;
        
        if(sum1 > sum2){
            long long tmp = q1.front();
            q1.pop();
            q2.push(tmp);
            sum1 -= tmp;
            sum2 += tmp;
        }
        else{
            long long tmp = q2.front();
            q2.pop();
            q1.push(tmp);
            sum2 -= tmp;
            sum1 += tmp;
        }
        
        answer++;
        
    }
    return -1;
}

 

 

처음에 했을 때 테스트 케이스 2개 정도가 시간초과가 발생했다. 이는 마지막의 return -1을 작성하는 것, 그리고 while부분의 조건을 answer <= queue1.size() * 3로 변경해서 해결했다. 

 

while문 조건에서 *2를 3으로 고쳐 시간초과를 해결했다. 이는 아무래도 *2보다 더 반복해서 해결해야하는 케이스가 있던 것 같다.