프로그래머스 (C/C++) 118667 : 두 큐 합 같게 만들기

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

프로그래머스

---

풀이

각 벡터를 순회하며 합을 구한 후, 값을 쉽게 이동하기 위해 큐에 저장했다.

각 큐의 합을 비교(sum1 vs sum2)하여 합이 큰 큐 -> 작은 큐로 값을 이동했다.

무한루프를 방지하기 위해 모든 원소가 다시 제자리로 돌아오는 횟수인 size * 4를 maxCnt로 지정하고 실행했다.

 

코드 2는 큐 대신 벡터 1개를 사용, 인덱스를 이동하며 각 큐의 경계를 나누었다.

---

코드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, size = queue1.size();
    ll sum1 = 0, sum2 = 0;

    queue<int> q1, q2;
    
    // 각 배열의 합 구한 후, 주어진 배열을 큐로 이동
    for (int i = 0; i < size; i++) {
        sum1 += queue1[i];  q1.push(queue1[i]);
        sum2 += queue2[i];  q2.push(queue2[i]);
    }
    
    // 모든 수의 합이 홀수
    if ((sum1 + sum2) % 2)
        return -1;
    
    long long maxCnt = 4 * size;
    while (maxCnt--) {
        
        // 두 큐의 합이 같다면 return
        if (sum1 == sum2)
            return answer;
    
        if (sum1 < sum2) {
            int tmp = q2.front();
            q2.pop();   q1.push(tmp);
            sum1 += tmp; sum2 -= tmp;
        }
        else {
            int tmp = q1.front();
            q1.pop(); q2.push(tmp);
            sum1 -= tmp; sum2+= tmp;
        }
        answer++;
    }
    return -1;
}

 

코드2

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

using namespace std;
typedef long long ll;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0, size = queue1.size(), totalSize = size * 2;
    ll sum1 = 0, sum2 = 0;

    vector<int> v;
    int first = 0, last = size;
    
    // 각 배열의 합 구한 후, 주어진 배열을 벡터로 이동
    for (int i = 0; i < size; i++) {
        sum1 += queue1[i];  v.push_back(queue1[i]);
    }
    for (int i = 0; i < size; i++) {
        sum2 += queue2[i];  v.push_back(queue2[i]);
    }
    
    // 모든 수의 합이 홀수
    if ((sum1 + sum2) % 2)
        return -1;
    
    long long maxCnt = 4 * size;
    while (maxCnt--) {
        
        // 두 합이 같다면 return
        if (sum1 == sum2)
            return answer;
    
        if (sum1 < sum2) {
            int tmp = v[last];
            sum1 += tmp; sum2 -= tmp;
            last = (last + 1) % totalSize;
        }
        else {
            int tmp = v[first];
            sum1 -= tmp; sum2 += tmp;
            first = (first + 1) % totalSize;
        }
        answer++;
    }
    return -1;
}