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

문제

두 큐 합 같게 만들기

풀이

아이디어는 큐1의 총 합과 큐2의 총 합을 비교하여 큐1이 작으면 큐2에서 값을 하나 빼서(pop) 큐1으로 옮겨 넣는(push) 방식이다. 큐2의 총 합이 작으면 반대로!

문제는 단순히 이렇게 구현하면 11번 테스트케이스와 28번 테스트케이스만 시간초과가 나온다는 점이다.

처음에는 벡터로 push_back(), erase() 하는 방식이나 큐로 push(), pop() 하는 것이 연산 비용이 높아 시간초과가 발생하나? 싶어서 아예 값을 옮기는 과정을 없애고 대신 인덱스(주소값)으로 큐1의 시작지점, 큐2의 시작지점을 옮기는 방식으로 구현했다. 하지만 이 방법으로도 11번, 28번이 통과되지 않는다. (아래 캡쳐 사진을 보면 주소값으로 접근하는 방식이 더 빠르긴하다)

결국 찾은 해결 방법은 if(answer > 300000) return -1;로 answer가 300000이 넘어가면 루프에 걸려 빠져나오지 못하고 있다고 판단해 -1을 리턴해버리는 것이다. 다른 사람의 풀이를 참고해보면 answer > queue1.size()*3, answer > queue1.size()*5, answer > queue1.size()*2 + queue2.size()*2 등 다양한 조건으로 루프를 빠져나오도록 하고있다.

큐1의 시작 주소를 s1, 큐2의 시작 주소를 s2라고 하면, 큐1과 큐2를 합친 전체 큐에서 s1 또는 s2가 전체 큐의 끝까지 갔으면 -1을 리턴한다.

소스코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    long long sum1 = 0;
    long long sum2 = 0;

    int tmp = queue1.size();

    for (int i: queue1) {
        sum1 += (long long) i;
    }
    for (int i: queue2) {
        sum2 += (long long) i;
    }
    queue1.insert(queue1.end(), queue2.begin(), queue2.end());
    auto s1 = queue1.begin();
    auto s2 = s1+tmp;

    if((sum1+sum2)%2==1) return -1;

    bool flag = false;
    while (true) {
        if (s1 == s2) {
            break;
        }
        if (sum1 == sum2) {
            flag = true;
            break;
        } else if (sum1 > sum2) {
            answer++;
            sum1 -= *s1;
            sum2 += *s1;
            s1++;
            if (s1 == queue1.end()) return -1;
        } else if (sum1 < sum2) {
            answer++;
            sum2 -= *s2;
            sum1 += *s2;
            s2++;
            if (s2 == queue1.end()) return -1;
        }
    }
    if (!flag) answer = -1;

    return answer;
}

큐 사용하는 풀이

직관적인 풀이는 큐를 사용해서 값을 옮기는 방식. 이 경우 while문을 계속 돌지 않도록 탈출 조건을 추가해야 한다.

// queue 사용

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    long long sum1 = 0;
    long long sum2 = 0;

    queue<int> que1;
    queue<int> que2;

    for (int i: queue1) {
        sum1 += (long long) i;
        que1.push(i);
    }
    for (int i: queue2) {
        sum2 += (long long) i;
        que2.push(i);
    }

    if ((sum1 + sum2) % 2 == 1) return -1;

    bool flag = false;
    while (true) {
        if (answer > 300000) return -1;

        if (sum1 == sum2) {
            flag = true;
            break;
        } else if (sum1 > sum2) {
            answer++;
            sum1 -= que1.front();
            sum2 += que1.front();
            que2.push(que1.front());
            que1.pop();
        } else if (sum1 < sum2) {
            answer++;
            sum2 -= que2.front();
            sum1 += que2.front();
            que1.push(que2.front());
            que2.pop();
        }
    }
    if (!flag) answer = -1;

    return answer;
}

풀이 속도 비교

주소값을 사용하는 풀이가 큐로 값 하나씩 push() pop()하는 것보다 빠르다.

큐 사용하는 풀이