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

 이 문제는 그리디한 방식으로 풀었다. 일단 이 문제에서 입력 배열이 최대 30만의 길이를 가지고 있다. 즉, O(n) 이하의 알고리즘을 선택해야하고, 그리디, dp, 이분 탐색 등 O(n) 이하의 시간을 사용하는 알고리즘 중에 그리디가 이 문제와 맞다고 생각했다. dp를 사용하기에는 입력 배열의 크기가 너무 커 dp 배열을 만들 수 없을 것이라 판단했고, 정렬이 불가능하므로 이분 탐색도 불가능하다고 판단했다. 

 

 

 일단 base case로 두 배열의 총 합이 홀수면 절대 같게 나눌 수 없으므로 -1을 리턴한다. 그 다음 처음부터 두 배열의 각 합이 같으면 바로 0을 리턴했다.

 

 

 이 문제에서 핵심 아이디어는 두 배열 중 더 합이 큰쪽에서 작은 쪽으로 숫자를 보내줘야한다는 것이다. 그리고 어떻게 해도 같게 만들지 못할 때는 -1을 리턴해야하는데, 이 부분을 구현하는 것이 중요하다. 나는 처음에 map을 활용해서 배열의 상태에 따라 이미 방문한 상태이면 break를 하도록 구현했는데, 이런 방식으로는 시간 초과가 난다. 또한 상태 저장을 위해 입력 배열 그대로 벡터로 사용했는데, erase를 사용하면서 시간 초과가 나게 된다. 따라서 반드시 queue를 사용하여 시간을 줄여야 하고, 배열의 크기 * 4 정도를 최대 탐색 길이로 정해서 이 횟수를 넘어가면 -1을 리턴하도록 구현하여 정답을 얻어냈다.

 

 

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    
    queue<int> q1;
    queue<int> q2;
    
    // base case
    ll acc1 = 0;
    for (int q : queue1) {
        acc1 += q;
        q1.push(q);
    }
    ll acc2 = 0;
    for (int q : queue2) {
        acc2 += q;
        q2.push(q);
    }
    if ((acc1 + acc2) % 2 == 1) {
        return -1;
    }
    if (acc1 == acc2) {
        return 0;
    }
    
    int limit = queue1.size() * 4;
    int cnt = 0;
    while (true) {
        
        if (cnt > limit) {
            cnt = -1;
            break;
        }
        
        if (acc1 > acc2) {
            int fr = q1.front();
            acc1 -= fr;
            acc2 += fr;
            q1.pop();
            q2.push(fr);
        }
        else if (acc1 < acc2) {
            int fr = q2.front();
            acc2 -= fr;
            acc1 += fr;
            q2.pop();
            q1.push(fr);
        }
        else {
            break;
        }
        cnt++;
    }
    
    answer = cnt;
    
    return answer;
}