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

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

프로그래머스

 

#include <string>
#include <vector>
#include <list>
using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    list<int> l1;
    list<int> l2;
    long long sum1=0,sum2=0;
    for(int i=0;i<queue1.size();i++)
    {
        sum1+=queue1[i]; l1.push_back(queue1[i]);
    }
    for(int i=0;i<queue2.size();i++)
    {
        sum2+=queue2[i];l2.push_back(queue2[i]);
    }
    if(sum1==sum2)return 0;
    int maxCnt = (l1.size()+l2.size())*2;
    while(true)
    {
        if(sum1==sum2)break;
        if(answer>=maxCnt)break;
        if(sum1>sum2)
        {
            l2.push_back(l1.front());
            sum1-=l1.front();
            sum2+=l1.front();
            l1.pop_front();
        }
        else if(sum1<sum2)
        {
            l1.push_back(l2.front());
            sum2-=l2.front();
            sum1+=l2.front();
            l2.pop_front();
        }
        answer++;
    }
    if(answer==0||answer>=maxCnt)return -1;
    return answer;
}

 

주어진 vector를 큐로 생각하고 한번의 동작은 하나의 큐에서 pop 후 다른 큐에 push 하는 것이다. 

이 때, 최소한의 동작으로 듀 큐의 원소의 합을 같게 만드려면 몇번의 동작이 필요한지 계산하는 문제이다. 

 

간단하게 접근했다. 

현 상황에서는 두 큐의 합 중 더 작은 쪽으로 원소를 이동시키는 것이 두 수의 합을 같게 만드는 최선의 방법이다. 

따라서 그 순간순간 최선의 결과를 선택하는 그리디 방법을 택했다. 

 

int answer = 0;
    list<int> l1;
    list<int> l2;
    long long sum1=0,sum2=0;
    for(int i=0;i<queue1.size();i++)
    {
        sum1+=queue1[i]; l1.push_back(queue1[i]);
    }
    for(int i=0;i<queue2.size();i++)
    {
        sum2+=queue2[i];l2.push_back(queue2[i]);
    }

vector 데이터를 list로 옮기며 각 큐의 원소합을 구한다.

 

if(sum1==sum2)return 0;
    int maxCnt = (l1.size()+l2.size())*2;
    while(true)
    {
        if(sum1==sum2)break;
        if(answer>=maxCnt)break;
        if(sum1>sum2)
        {
            l2.push_back(l1.front());
            sum1-=l1.front();
            sum2+=l1.front();
            l1.pop_front();
        }
        else if(sum1<sum2)
        {
            l1.push_back(l2.front());
            sum2-=l2.front();
            sum1+=l2.front();
            l2.pop_front();
        }
        answer++;
    }

애초에 동일하면 0을 리턴하고 최대 카운트를 정해둔다. (최대는 모든 원소가 2번씩 움직여 원래 두 큐의 모습이 되는 것이다.)

 

그리고 while문을 통해 더 합이 작은쪽으로 원소를 하나씩 이동시키고 answer를 증가시킨다. 

합이 같아지거나 maxCnt를 넘으면 종료된다. 

 

if(answer==0||answer>=maxCnt)return -1;

만약 maxCnt를 넘어섰다면 -1을 리턴한다. 같아지는 경우가 없다는 뜻이기 때문이다. 

 

문제를 풀고 너무 긴 실행시간과 3개의 테스트케이스 실패가 떴다. 

아무래도 vector는 원소의 삽입,삭제를 많이하기에는 불리하다는 판단이 들어 erase로 맨 앞 원소를 제거하는 대신

list를 사용하여 시간을 단축시켰더니 해결되었다. 

 

또,

if(sum1==sum2)return 0;
    int maxCnt = (l1.size()+l2.size())*2;

애초에 같은 경우를 체크하지 않아서 answer가 0인경우 -1이 리턴되었기 때문에 if문을 추가하였다.

또, 원소가 한번씩 이동하여 두 큐의 원소만 바뀐 경우가 최대라고 생각했는데

[1,1,1,1] , [1,1,7,1] 같은 경우는 최대 *2 까지 이동이 가능해서 바꿨더니 통과했다. 

 

이런 예외적인 상황이나 경우의 수를 미리 파악해서 코드로 예방하는 것이 항상 어려운 것 같다.