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

두 큐 합 같게 만들기

문제 링크

두 큐 합 같게 만들기

분석

queue1과 queue2의 원소의 크기가 최대 $10^9$이므로, 각 배열의 합을 구한다면 long long을 사용해야합니다.

합을 같게 만들기 위해 필요한 작업의 최소 횟수를 반환해야합니다.
만약, 같은 합을 만들 수 없다면 -1을 반환해야합니다.

문제 설명은 큐를 사용한 설명입니다.

풀이

#include <vector>
#include <queue>
#include <numeric>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    
    long long sum1 = accumulate(queue1.begin(), queue1.end(), 0);   // queue1의 총합
    long long sum2 = accumulate(queue2.begin(), queue2.end(), 0);   // queue2의 총합
    unsigned long long total = sum1 + sum2; // 전체 총합
    
    // 홀수인 경우 같은 합을 만들 수 없으므로 -1 반환
    if (total % 2 == 1)
    {
        return -1;
    }
    
    int maxCount = queue1.size() * 3 - 3;   // 최대 횟수
    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)
        {
            sum1 -= q1.front();
            sum2 += q1.front();
            q2.push(q1.front());
            q1.pop();
        }
        else if (sum1 < sum2)
        {
            sum2 -= q2.front();
            sum1 += q2.front();
            q1.push(q2.front());
            q2.pop();
        }
        
        ++answer;
        
        // 최대 횟수를 넘었다면 합을 같게 만들 수 없다.
        if (answer > maxCount)
        {
            return -1;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• accumulate 함수 $O(n)$
• 큐 초기화하는 반복문 $O(n)$
• 큐 원소 이동 $O(n)$
• $O(n + n + n)$

공간 복잡도는 $O(n)$입니다.

• 두 개의 큐 $O(n + n)$

테스트 1 〉 통과 (0.01ms, 4.14MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.01ms, 4.16MB)
테스트 4 〉 통과 (0.01ms, 4.14MB)
테스트 5 〉 통과 (0.01ms, 4.12MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 3.68MB)
테스트 8 〉 통과 (0.01ms, 4.22MB)
테스트 9 〉 통과 (0.02ms, 4.2MB)
테스트 10 〉 통과 (0.03ms, 4.15MB)
테스트 11 〉 통과 (1.00ms, 7.03MB)
테스트 12 〉 통과 (0.77ms, 7.06MB)
테스트 13 〉 통과 (0.87ms, 8.35MB)
테스트 14 〉 통과 (1.00ms, 8.9MB)
테스트 15 〉 통과 (1.19ms, 9.79MB)
테스트 16 〉 통과 (0.97ms, 10.3MB)
테스트 17 〉 통과 (1.25ms, 10.6MB)
테스트 18 〉 통과 (3.69ms, 25.4MB)
테스트 19 〉 통과 (3.44ms, 25.6MB)
테스트 20 〉 통과 (4.21ms, 25.6MB)
테스트 21 〉 통과 (4.30ms, 25.9MB)
테스트 22 〉 통과 (4.98ms, 25.9MB)
테스트 23 〉 통과 (4.00ms, 27MB)
테스트 24 〉 통과 (4.81ms, 26.9MB)
테스트 25 〉 통과 (0.01ms, 4.2MB)
테스트 26 〉 통과 (0.01ms, 4.2MB)
테스트 27 〉 통과 (0.01ms, 4.14MB)
테스트 28 〉 통과 (1.70ms, 10.8MB)
테스트 29 〉 통과 (0.15ms, 4.29MB)
테스트 30 〉 통과 (2.73ms, 10.9MB)