두 큐 합 같게 만들기 (feat. 프로그래머스, 118667번)

두 큐 합 같게 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <string>
#include <vector>
using namespace std;
int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0, queue_size = queue1.size(), queue1_idx = 0, queue2_idx = 0;
    long long sum1 = 0, sum2 = 0;
    for (auto& v : queue1)
        sum1 += v;
    for (auto& v : queue2)
        sum2 += v;
    while (answer <= (queue_size << 2)){
        if (sum1 < sum2) {
            sum1 += queue2[queue2_idx];
            sum2 -= queue2[queue2_idx];
            queue1.push_back(queue2[queue2_idx++]);
        }
        else if (sum2 < sum1) {
            sum2 += queue1[queue1_idx];
            sum1 -= queue1[queue1_idx];
            queue2.push_back(queue1[queue1_idx++]);
        }
        else {
            return answer;
        }
        ++answer;
    }
    return -1;
}
// *&)*@*

 

1. 문제로 주어진 vector를 그대로 사용해도 되고, 문제의 요구사항인 queue를 정의해서 사용해도 될 것 같습니다.
2. 문제의 지문상으로는 한쪽의 queue를 꺼내 다른쪽에 삽입하는 조건이지만, erase가 일어날수록 효율이 떨어지므로 erase 조건에서 인덱스를 한칸씩 증가시켰습니다.
3. sum1 < sum2 인 경우, queue2를 꺼내 queue1에 넣습니다.
4. sum2 < sum1 인 경우, queue1을 꺼내 queue2에 넣습니다.
5. 총 합의 절반값을 구할 필요는 없습니다. sum1 == sum2인 경우가 총 합의 절반값과 동일하기 때문입니다.