[Programmers Level2] 두 큐 합 같게 만들기(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

프로그래머스

 

[문제 설명]

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

 

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

 

다음은 두 큐를 나타내는 예시입니다.

 

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

 

두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

 

1. queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
2. queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.

따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

 

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

 

[제한 사항]

 

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

 

[입출력 예]

 

queue1	queue2	result
[3, 2, 7, 2]	[4, 6, 5, 1]	2
[1, 2, 1, 2]	[1, 10, 1, 2]	7
[1, 1]	[1, 5]	-1

 

 

[입출력 예 설명]

 

입출력 예 #1

문제 예시와 같습니다.

 

입출력 예 #2

두 큐에 담긴 모든 원소의 합은 20입니다. 따라서, 각 큐의 합을 10으로 만들어야 합니다. queue2에서 1, 10을 순서대로 추출하여 queue1에 추가하고, queue1에서 1, 2, 1, 2와 1(queue2으로부터 받은 원소)을 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [10], queue2는 [1, 2, 1, 2, 1, 2, 1]가 되며, 각 큐의 원소 합은 10으로 같습니다. 이때 작업 횟수는 7회이며, 이보다 적은 횟수로 목표를 달성하는 방법은 없습니다. 따라서 7를 return 합니다.

 

입출력 예 #3

어떤 방법을 쓰더라도 각 큐의 원소 합을 같게 만들 수 없습니다. 따라서 -1을 return 합니다.

 

[문제 풀이]

 

간단하게 정리하자면 아래와 같다.

 

1. vector의 경우 뒤에서 값을 넣거나 빼는 동작만 가능하기 때문에 queue로 변경

2. 각 총합을 계산하기 위해 accmulate 함수를 사용

2-1. 만약 두 개의 총 합을 2로 나누었을 때 나머지가 존재한다면(홀수일 때) 두 개를 동일하게 만들 수 없으므로 -1로 리턴

3. 두 개의 각 총 합을 확인하여 같은 경우 0으로 리턴(push하거나 pop하는 동작이 불필요!)

4. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업 최소 횟수를  구하기 위해서는 총 합이 큰 큐에서 작은 큐로 원소를 옮기는 것이 최적!!!

 

하지만? 총 합이 큰 큐에서 작은 큐로 원소를 옮기기만해서는 무한으로 옮겨질 가능성이 있다.

여기서 조건이 필요한데..

 

처음 내 생각으로는 큐의 사이즈*2만큼만 확인을 한다면 각 큐 원소들을 옮기고 빼고를 다 확인 가능할 줄 알았다.

그러나.. 테스트 케이스 1번에서만 실패..

 

반례를 생각해보다가 이런 반례가 있는 것을 알아냈다.

 

queue1 = [1, 1, 1, 1]
queue2 = [1, 1, 7, 1]

 

이 반례의 경우 같게 만들기 위해 필요한 작업 최소 횟수가 9로 나온다.

그렇다면, 큐의 사이즈*2 보다 더 많이 확인해야하는 경우가 있다는 것이다.

그래서 최대로 확인 하는 횟수를 큐의 사이즈*3으로 하여 확인 횟수를 늘려서 통과할 수 있었다.

 

5. 마지막으로 각 총합을 확인하여 같다면 확인한 횟수를 리턴

같지 않다면 -1를 리턴

 

 

[최종 코드]

 

 

[GitHub]

 

Programmers/[Level2]/Make_the_sum_of_the_two_queue_equal.cpp at main · SmallPeanutPark/Programmers

 

#include <string>
#include <vector>
#include <utility>
#include <numeric>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;

pair<queue<long long>, queue<long long>> init(vector<int> v1, vector<int> v2) {

    queue<long long> t1;
    queue<long long> t2;

    for(auto element : v1) {
        t1.push(element);
    }

    for(auto element : v2) {
        t2.push(element);
    }

    return make_pair(t1, t2);
}

int solution(vector<int> v1, vector<int> v2) {
    int answer = 0;
    int len = v1.size();
    // step 1. vector에서 queue로 자료형 변경
    pair<queue<long long>, queue<long long>> pairlist = init(v1, v2);

    // step 2. pair 에서 각 queue로
    queue<long long> q1 = pairlist.first;
    queue<long long> q2 = pairlist.second;

    // step 3. vector 총합 계산
    long long q1Sum = accumulate(v1.begin(), v1.end(), 0);
    long long q2Sum = accumulate(v2.begin(), v2.end(), 0);

    // step 4. 만약 두 개의 총합을 나누었을 때 나머지가 존재하면 동일하게 만들 수 없음
    unsigned long long totalSum = q1Sum + q2Sum;
    if(totalSum % 2 != 0) return -1; 

    // step 5. 두개의 합이 같은 경우, 횟수 0
    if(q1Sum == q2Sum) return answer;
    else {
        /* step 6. 두개의 합이 같지 않은 경우 확인 필요
        확인하는 횟수는 두개의 길이합보다 더 많은 횟수를 확인해야함. 반례 존재
        */
        while((q1Sum != q2Sum) && ((len*3) != answer)) {
            long long q1Front = q1.front();
            long long q2Front = q2.front();
            // step 7. 총 합이 큰 곳에서 작은 곳으로 값을 더해줘야함
            if(q1Sum < q2Sum) {
                q1Sum += q2Front;
                q2Sum -= q2Front;
                q1.push(q2Front);
                q2.pop();
            } else {
                q2Sum += q1Front;
                q1Sum -= q1Front;
                q2.push(q1Front);
                q1.pop();
            }
            answer += 1;
        }
    }

    if(q1Sum == q2Sum) return answer;
    else answer = -1;

    return answer;
}