프로그래머스 레벨2 <두 큐 합 같게 만들기> C++ 풀이

처음 제출을 하고 테스트케이스 1번은 실패 그리고 11번과 30번대에서 시간초과를 하나씩 받았습니다. 

시간초과기 때문에 while문을 유심히 살펴봤습니다. 결국 종료 조건을 통과하지 않는 경우의 수가 존재하는건데, 그 케이스를 처리하지 못하기 때문이라 생각하고 반례를 생각해봤습니다. 그리고 처음 든 생각은 [2,2,2,2] [2,2,2]과 같은 경우에는, 코드대로 큰 큐에서 작은큐로 이동할 것이기 때문에 2 하나가 무한으로 왔다갔다 하면서 cnt만 올라가니 cnt를 제한해야 한다고 생각했습니다.

 

그래서 cnt의 제한을 어떻게 두어야 하나 고민하다가, 큐1과 큐2의 사이즈를 더한거보다 커지면 두 큐의 합을 같게 만들지 못하는걸로 결론내리고 제출했습니다. 그리고 1번은 그대로 실패. 11번과 30번의 시간초과를 정답으로 채점받았습니다. 그리고 한참 더 풀어보는데 1번이 안풀려 질문 게시판에서 반례를 확인했습니다. 

 

[3,3,3,3] [3,3,21,3] 같은 경우에는 [3,3,3,3,3,3,21] [3] 이렇게 이동시키면서 카운트를 +3 하고 [21] [3,3,3,3,3,3,3] 이렇게 다시 이동시키면서 카운트+6을 하면 총 9번의 움직임으로 두 큐의 합을 같게 할 수 있습니다. 결국 위에서 구현한 큐1사이즈+큐2사이즈를 넘는 케이스가 있는 것이지요. 안어려운듯 하면서 어려웠던 문제 였던것 같습니다... 특히 cnt를 제한하는 조건을 모든 케이스를 커버할 수 있게끔 잡아내는것이 쉽지 않았던 것 같습니다.

 

 

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int solve(long long val, queue<int> q1, queue<int> q2, long long q1sum, long long q2sum)
{
    //일단 큰놈에서 작은놈으로 옮기자
    long long cur1 = q1sum;
    long long cur2 = q2sum;
    int size = q1.size()*3;
    int cnt = 0;
 
    //계속 왔다갔다 하는경우 ? -> 이때는 결국 -1리턴이겠네.
    //핵심은 size를 몇으로 할지를 정하는것!!
    while (true) 
    {        
           
        if (cnt > size)
        {
            return -1;
        }
 
        if (cur1 < cur2)
        {
            int tmp = q2.front();
            q2.pop();
            q1.push(tmp);
            cur1 += tmp;
            cur2 -= tmp;
        }
        else if (cur1 > cur2)
        {
            int tmp = q1.front();
            q1.pop();
            q2.push(tmp);
            cur1 -= tmp;
            cur2 += tmp;
        }
        else
        {
            break;
        }
 
        cnt++;
    }
 
    return cnt;
}
 
int solution(vector<int> queue1, vector<int> queue2) {
    int answer = -1;
    queue<int> q1;
    queue<int> q2;
    long long total = 0;
    long long q1sum = 0, q2sum = 0;
 
    for (int i = 0; i < queue1.size(); i++)
    {
        q1.push(queue1[i]);
        total += queue1[i];
        q1sum += queue1[i];
    }
 
    for (int i = 0; i < queue2.size(); i++)
    {
        q2.push(queue2[i]);
        total += queue2[i];
        q2sum += queue2[i];
    }
 
    if (total % 2 != 0)
        return -1;
    if (q1sum == q2sum)
        return 0;
 
    long long goal = total / 2;
 
 
    return solve(goal, q1, q2, q1sum, q2sum);
}