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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 여러 방법으로 풀 수 있는 문제다.

 

누적합을 이용해 푸는 방법, 문제 그대로 Queue를 이용해 푸는 방법, index를 이용해 Queue가 pop되는 것 처럼 푸는 방법 등 다양한 방법이 존재한다.

 

이 중에서 나는 Index를 이용해 풀었다.

 

먼저 이 문제에서 중요한 점은 Queue에서 뺀 원소는 다른 Queue에 들어간다는 것이다.

 

즉, 그림으로 생각하면 아래와 같이 Queue를 표현할 수 있다.

 

여기서 Queue2의 원소가 Queue1으로 삽입된다면, 위 그림과 같이 파란 색 부분의 합이 Queue1에 들어가게 된다.

 

이렇게 연속적인 수들의 합이 되기 때문에 누적합이나, 단순히 Index를 이용해 풀 수 있는 것이다.

 

기본적으로 문제를 푸는 방법은 아래와 같다.

 

1. Queue1과 Queue2의 원소들의  합을 비교하고 만약 Queue1과 Queue2가 같다면, 그 때 까지 이동한 원소들의 횟수를 return 한다.

 

2. 만약 Queue1의 원소들의 합 > Queue2의 원소들의 합이라면 Queue1의 원소를 pop해 Queue2에 넣는다.

 

3. 만약 Queue1의 원소들의 합 < Queue2의 원소들의 합이라면 Queue2의 원소를 pop해 Queue1에 넣는다.

 

그렇다면 위 과정을 얼마나 반복해야 할까?

 

정답은 최대 3n-3번이다.

 

아래 그림을 보며 생각해 보자.

 

st의 최대 범위가 n-1인 이유는 n-1을 넘어가는 경우는 결국 queue2에 queue1의 모든 원소가 이동했다는 뜻이다.

그러므로 반대로 queue2의 원소를 빼 queue1에 넣는 경우와 같은 경우다.

 

그래서 st가 n을 넘어가는 경우는 정답이려면 이전에 queue2에서 queue1에 원소를 넣는 경우에서 정답이 존재 해야하기 때문에 st가 n을 넘어가는 경우는 고려할 필요가 없다.

 

그러므로 st의 최대 범위는 (n-1)번 이동하는 경우다.

 

이제 ed의 최대 범위를 알아보자 

 

마찬가지로 ed가 최대 범위가 되려면 st의 최대범위를 포함하지 않아야 한다.

 

즉, st의 최대 범위인 n-1을 포함하지 않으면서 최대인 값은 Queue2를 옮기는(n) + Queue1을 옮기는 (n-2)로 최대 이동 횟수는 2n-2가 된다.

 

그러므로 st와 ed의 이동횟수를 합친 3n - 3이 Queue1과 Queue2가 같도록 만드는 원소의 최대 이동 횟수가 된다.  

 

좀 더 쉽게 최대 이동 횟수를 두 개의 Queue 그림으로 표현하면 아래의 경우에 최대 횟수다.

 그러므로 이동횟수가 3n-3보다 작을 때 까지만, Queue에서 원소들이 이동하도록 코드를 구현하면 된다.

 

​

 

[아이디어 정리]

1. Queue1과 Queue2의 원소들의 합을 계산한 다음 Queue1의 합과 Queue2의 합의 크기를 비교한다.
2. 합의 크기를 비교한 뒤 크기가 같다면 이동횟수를 return한다.
3. 합의 크기가 다르면, 더 크기가 큰 Queue에서 작은 Queue로 원소를 이동시켜 합을 계산한다.
4. 위 과정을 최대 3n-3번 반복한 후에도 같지 않으면 불가능하므로 -1을 return 한다.

 

 

 

Code

 

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    long long qSum=0, qSum2=0;
    for (int i=0; i<queue1.size(); i++)
    {
        qSum+=queue1[i],qSum2+=queue2[i];
    }
    int i=0,j=0;
    bool flag1=false, flag2=false;
    while (answer<=queue1.size()*3-3)
    {
        if (i>=queue1.size())
        {
            i=0;
            flag1=!flag1;
        }
        if (j>=queue1.size()){
            j=0;
            flag2=!flag2;
        } 
        if (qSum>qSum2)
        {
            if (!flag1)
            {
                qSum-=queue1[i];
                qSum2+=queue1[i];    
            }
            else
            {
                qSum-=queue2[i];
                qSum2+=queue2[i];  
            }
            i++, answer++;
        }
        else if (qSum<qSum2)
        {
            if (!flag2)
            {
                qSum2-=queue2[j];
                qSum+=queue2[j];
            }
            else{
                qSum2-=queue1[j];
                qSum+=queue1[j];
            }
            j++,answer++;
        }
        else
        {
            return answer;
        }
    }
    return -1;
}

 

---

처음에는 누적합으로 구하려다가 그냥 index로 구하고 싶어서 코드를 구현햇는데, 괜히 복잡해졌다.

불가능하다고 판단하기 위한 최대 이동 횟수가 떠오르지 않으면 생각보다 고민하게 될 문제였던 것 같다.

프로그래머스