두 큐 합 같게 만들기

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=cpp

단순 그리디

문제를 보자마자 그리디 알고리즘을 떠올렸다. 그리디는 일반적으로 가능한 모든 방식이 다 불가능하다고 판단될 때, 적용하는 것이 효과적이지만 문제를 보자마자 그리디를 떠올리게 되어, 바로 접근해보았다.

먼저, -1을 반환하는 경우로 두 가지를 찾았다.

• 두 큐의 합이 같아야 하므로, 전체 수의 합은 짝수여야 한다.
• 특정 한 수가 전체 큐의 합의 절반보다 크지 않아야 한다.

위 두 가지 조건을 필터링한 이후에는, 반복문을 기반으로 합이 큰 쪽에서 작은 쪽으로 옮겨주는 방식으로 구현했다.
구현하다 보니, 시간 초과가 날 것이라는 확신이 생겼지만 확인차 제출해본 결과 73.3/100.0을 받았다.

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0, max_num = 0; // 전체 수의 합: total, 가장 큰 수: max_num
    ll sum_1 = 0, sum_2 = 0, total = 0;
    
    for(auto value: queue1) {
        total += value;
        max_num = max(max_num, value);
        sum_1 += value;
    }
    for(auto value: queue2) {
        total += value;
        max_num = max(max_num, value);
        sum_2 += value;
    }
    
    // 총합이 홀 수이거나, 특정 원소가 절반보다 큰 경우
    if(total % 2 != 0 || total / 2 < max_num) {
        return -1;
    }
    
    while(sum_1 != sum_2) {
        if(sum_1 > sum_2) {
            int now = queue1.front();
            queue1.erase(queue1.begin());
            queue2.push_back(now);
            sum_1 -= now;
            sum_2 += now;
            answer++;
        } else {
            int now = queue2.front();
            queue2.erase(queue2.begin());
            queue1.push_back(now);
            sum_2 -= now;
            sum_1 += now;
            answer++;
        }
    }
    
    return answer;
}

개선된 그리디 - 종료 조건 추가

시간초과를 해결할 수 있는 방법이 무엇일까를 생각해보았다. 바로, 위에 언급되었던 두 조건이 아니더라도 -1이 되는 경우에 대하여 위의 코드로는 판단할 수 없다는 것이다. -1로 간주해야 하는 기준으로는 처음과 동일한 상태가 되는 최소 횟수를 찾고자 했다.
이를 생각할 때, 문제의 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업이라는 문장에서 아이디어를 얻었다.
두 개의 큐를 연결해놓은 뒤 첫 번째 큐를 의미하는 시작 idx와 끝 idx를 지정한다. 이후, 해당 idx들을 이동시키면서 첫 번째 큐가 어떤 값을 가지고 있는지를 확인하면서 순회하게 된다는 가정을 잡으면 처음과 동일한 상태가 되는 최소 횟수를 계산할 수 있다.
두 개의 큐를 연결했기에, 총 길이는 2N이 된다. 첫 번째 큐의 시작 idx가 다시 첫 번째로 돌아오게 된다면, 사실상 동일한 탐색을 재시작하는 상태가 됨을 추측할 수 있다. 그렇기에, 총 4N의 횟수를 초과하는 순간 -1로 간주하면 시간 초과를 해결할 수 있을 것이다.

개선된 방식을 적용한 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0, max_num = 0; // 전체 수의 합: total, 가장 큰 수: max_num
    ll sum_1 = 0, sum_2 = 0, total = 0;
    int limit_cnt = queue1.size() * 4;
    
    for(auto value: queue1) {
        total += value;
        max_num = max(max_num, value);
        sum_1 += value;
    }
    for(auto value: queue2) {
        total += value;
        max_num = max(max_num, value);
        sum_2 += value;
    }
    
    // 총합이 홀 수이거나, 특정 원소가 절반보다 큰 경우
    if(total % 2 != 0 || total / 2 < max_num) {
        return -1;
    }
    
    while(sum_1 != sum_2) {
        if(sum_1 > sum_2) {
            int now = queue1.front();
            queue1.erase(queue1.begin());
            queue2.push_back(now);
            sum_1 -= now;
            sum_2 += now;
            answer++;
        } else {
            int now = queue2.front();
            queue2.erase(queue2.begin());
            queue1.push_back(now);
            sum_2 -= now;
            sum_1 += now;
            answer++;
        }
        
        if(answer > limit_cnt) {
            return -1;
        }
    }
    
    return answer;
}

이번엔, 80.0/100.0을 받았다.

개선된 그리디 2 - 배열 대신 큐

개선했음에도 불구하고, 계속 시간 초과가 나는 경우가 존재했다. 이를 해결하고자 vector를 queue로 변경했다. queue는 FIFO구조이기에, pop()으로 첫 번째 데이터를 지우는 과정에서 O(1)의 상수시간이 필요하지만, vector는 erase()로 데이터를 지우는 과정에서 O(N)의 시간이 필요하기 때문이다.

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0, max_num = 0; // 전체 수의 합: total, 가장 큰 수: max_num
    ll sum_1 = 0, sum_2 = 0, total = 0;
    int limit_cnt = queue1.size() * 4;
    queue<int> q1, q2;
    
    for(auto value: queue1) {
        total += value;
        max_num = max(max_num, value);
        sum_1 += value;
        q1.push(value);
    }
    for(auto value: queue2) {
        total += value;
        max_num = max(max_num, value);
        sum_2 += value;
        q2.push(value);
    }
    
    // 총합이 홀 수이거나, 특정 원소가 절반보다 큰 경우
    if(total % 2 != 0 || total / 2 < max_num) {
        return -1;
    }
    
    while(sum_1 != sum_2) {
        if(sum_1 > sum_2) {
            int now = q1.front();
            q1.pop();
            q2.push(now);
            sum_1 -= now;
            sum_2 += now;
            answer++;
        } else {
            int now = q2.front();
            q2.pop();
            q1.push(now);
            sum_2 -= now;
            sum_1 += now;
            answer++;
        }
        
        if(answer > limit_cnt) {
            return -1;
        }
    }
    
    return answer;
}

위 개선 과정을 통해서 정답 판정을 받을 수 있었다. 시간 초과를 고민하기 위해 4*N을 기준점으로 잡는 과정이 도움 없이 해결하기에 굉장히 까다로웠던 것 같다. 세밀한 조건들을 고민하는 과정을 놓치지 않는 연습을 해야겠다.