[구간합] 두 큐 합 같게 만들기 - 2022 KAKAO TECH INTERNSHIP

해결 방법

입출력 예 #1를 이용하여 해결 방법을 설명해보겠다.

필자는 2개의 큐를 각각 다른 순서로 결합한 2개의 벡터를 만들어놓고 구간합을 이용해서 해결했다. 

2개의 결합 벡터를 만든 이유는 모든 구간합을 편하게 계산하기 위함이다. 2개의 결합 벡터는 다음과 같다. 

 

그리고 각 큐의 합은 두 큐의 합의 1/2이어야 하기 때문에 구간합이 15인 구간을 따로 선정했다. 각 결합 벡터에 대한 누적합 벡터를 따로 만들어서 이 누적합 벡터에 투포인트 알고리즘을 적용해서 구간합을 구하는 것이 효율적이다.

이제 특정 구간합만 왼쪽 큐에 모을 수 있게 해보자. 큐의 원소는 한쪽으로만 들어오고 다른 한쪽으로만 나간다는 특성을 이용해서 들어오는 원소의 개수와 나가는 원소의 개수를 합하기만 하면 작업 횟수를 구할 수 있다. 잘 이해가 안간다면 아래 이미지와 소스코드를 보면 도움이 될 것이다.

 

 

소스 코드

#include <vector>
using namespace std;
int answer = 600001;

// 누적합 벡터 반환
vector<long long> get_cumulative_vector(vector<int> v) {
    vector<long long> accv;
    accv.push_back(0); // 계산의 편의를 위해 0을 첫 번째 원소로 추가
    for(int i=0;i<v.size();i++) accv.push_back((long long)(v[i]+accv[i]));
    return accv;
}

// 최소 이동 수 계산
void calculate_moves(vector<long long> accv, int queue_size, long long sum) {
    int s=0, e=1;
    while(e<=queue_size*2&&s<e) {
        if(accv[e]-accv[s]==sum/2) {
            if(e>=queue_size) answer=min(answer, s+e-queue_size);
            s++;
        } else if(accv[e]-accv[s]>sum/2) s++;
        else e++;
    }    
}

int solution(vector<int> queue1, vector<int> queue2) {
    int qsize = queue1.size();
    vector<int> combv1; // queue1 + queue2
    vector<int> combv2; // queue2 + queue1
    
    for(int i=0;i<qsize;i++) {
        combv1.push_back(queue1[i]);
        combv2.push_back(queue2[i]);
    }
    for(int i=0;i<qsize;i++) {
        combv1.push_back(queue2[i]);
        combv2.push_back(queue1[i]);
    }
    
    // 누적합 벡터와 두 큐에 담긴 모든 원소의 합 구하기
    vector<long long> accv1 = get_cumulative_vector(combv1);
    vector<long long> accv2 = get_cumulative_vector(combv2);
    long long sum=accv1[qsize*2];
    
    // 최소 이동 수 계산 및 결과 반환
    calculate_moves(accv1, qsize, sum);
    calculate_moves(accv2, qsize, sum);
    if(answer==600001) return -1;
    return answer;
}

 

 

테스트케이스 30개 모두 정답

 

 

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