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

📢 문제 설명

---

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 
추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 
이때 필요한 작업의 최소 횟수를 구하고자 합니다. 
한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.
큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 
이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 
즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 
예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 
이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.
길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 
각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 
단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

🏕 제한사항

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

---

🥝 풀이

해당 문제를 위해서 다음과 같은 고려사항을 설정하였다.
1. queue1의 이동횟수가 기존 queue1의 크기와 같으면서 queue2의 이동횟수가 기존 queue2의 크기와 같으면 두 queue의 원소가 서로 교환되었다고 판단하고 -1을 return
2. 두 queue의 원소의 합이 홀수인 경우 두 queue의 합이 같을 수 없으므로 -1 return
3. queue의 이동횟수의 합이 60만을 넘으면 (최대 queue원소의 크기가 30만이므로) -1 return

이후 어떤 방식으로 queue들의 원소를 이동하면 좋을지 생각해보았다.
먼저 각 queue의 원소의 합을 que1_sum, que2_sum라는 변수에 각각 할당해주었다.

이후 que1_sum와 que2_sum를 비교하여 더 큰 값을 가지는 queue의 원소를 작은 값을 가지는 queue로 이동시키는 행위를 반복하도록 했다.

위와 같은 예시가 있다고 할 때, queue1의 전체 합은 6 이며 queue2의 합은 14가 된다. 따라서 queue1의 합이 더 작기 때문에 queue2의 첫번째 원소를 queue1에 넣어주면 아래와 같은 결과를 갖게 된다.

queue1에 첫번째 원소를 넣어주었음에도 전체 합계가 queue1이 더 작기 때문에 queue2 에서 다시 queue1에 원소를 push 해준다.

그렇게 되면 queue1의 합이 queue2의 합보다 커지게 되며, 이경우 queue2에 queue1의 원소를 push 해준다.

위의 과정을 두 queue가 같을때 까지 반복한다.

(위의 경우 queue2의 마지막에 원소 1이 들어가지 않았다 -> 오타!)
그렇게 되면 위와 같이 queue 가 성립하게 된다.

옮긴 횟수는 총 7이 됨을 알 수 있다. (빠진 원소 1포함)

🐷 코드

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

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = -2;
    int que1_cnt = 0, que2_cnt = 0, que1Size = queue1.size(), que2Size = queue2.size();
    long long que1_sum = 0, que2_sum = 0;
    queue<int> que1, que2;
    
    for (int i = 0; i < que1Size; i++) {
        que1_sum += queue1[i];
        que1.push(queue1[i]);
    }
    for (int i = 0; i < que2Size; i++) {
        que2_sum += queue2[i];    
        que2.push(queue2[i]);
    }
    
    if ((que1_sum + que2_sum) % 2 == 1) return -1;
    while(que1_sum != que2_sum && que1_cnt + que2_cnt < 600000) {
        int num;
        if (que1_cnt == que1Size && que2_cnt == que2Size) return -1;
        if (que1_sum > que2_sum) {
            // queue1[0] -> queue2, que2_sum up, que1_sum down 
            num = que1.front();
            que2.push(num);
            que2_sum += num;
            que1_sum -= num;
            
            // que1_cnt up -> move
            que1_cnt += 1;
            que1.pop();
        }
        else {
            // queue2[0] -> queue1, que1_sum up, que2_sum down
            num = que2.front();
            que1.push(num);
            que1_sum += num;
            que2_sum -= num;
            
            // que2_cnt up -> move
            que2_cnt += 1;
            que2.pop();
        }
    }
    
    if (que1_cnt + que2_cnt >= 600000 && que1_sum != que2_sum) answer = -1;
    else answer = que1_cnt + que2_cnt;
    return answer;
}

🥉 어려웠던 점

1. 시간초과(제한사항에 대한)
→ 최대 30만개의 원소를 가질 수 있기 때문에 중간에 제한을 두지 않으면 시간초과가 발생하는 것을 확인하였다. 제한사항에 대한 부분을 숙지하는 습관을 조금 더 들여야할 것 같다.
2. 시간초과(vector의 erase()함수)
→ 테스트케이스24 번에 대한 경우 계속된 시간초과로 애를 먹었다.
→ vector의 erase() 함수의 시간복잡도가 O(n) 이기 때문에 최대 600000 * 300000 까지 커질 수 있기 때문에 시간초과가 발생한다는 것을 알게 되었다.
→ 따라서 vector의 원소를 queue에 넣어 pop() 을 이용하여 시간초과를 해결하였다. pop()의 경우 시간복잡도가 O(1) 이기 때문에 큰 문제가 없었다.