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

문제

 

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

프로그래머스

 

문제풀이

 

큐를 pop 하고 다른 큐로 push 하는 작업을 묶어서 횟수를 센다.

큐 두 개를 붙여 한 벡터처럼 생각하고 투포인터를 이용해서 문제를 풀었다.

 

투 포인터를 이용해 left, right부분을 설정하고 합을 구하면서 비교한다.

합이 K보다 크면 left부분을 sum에서 빼고, 합이 K보다 작으면 right부분을 sum에 더한다.

이러면서 모든 경우를 탐색한다.

 

만약 sum이 K와 같다면 3가지 경우로 나눌 수 있다.

 

1. 첫 번째 경우

 

queue1과 queue2를 붙인 elements벡터이다.

가운데를 기준으로 왼쪽은 queue1, 오른쪽은 queue2이다.

큐에서 추출하여 다른 큐에 추가하게 되면 위 그림에서는 맨 왼쪽칸이 맨 오른쪽 끝으로 이동하는 식이다.

회색 부분이 현재 sum에 해당하는 부분이다.

 

이 경우에는 회색칸 2칸만 queue2에 있는 것이 최소 횟수이다.

 

먼저 회색칸까지 queue2에 옮긴다. 횟수는 right이다.

 

그다음 queue2의 모든 흰색칸을 queue1로 옮긴다. 횟수는 left + queue2.size()이다.

총 right + left + queue2.size() 회이다.

 

 

2. 두 번째 경우

 

회색칸을 queue1로 이동하는 것이 가장 적은 횟수일 것이다.

queue1의 흰 칸을 queue2로 옮긴다. 횟수는 left이다.

queue2의 회색칸을 queue1로 옮긴다. 횟수는 right - q1.size()이다.

총 left + (right - queue1.size()) 회이다.

 

 

3. 마지막 경우

queue2의 회색칸을 queue1로 옮기는 것이 가장 적은 횟수일 것이다.

 

queue2의 회색칸을 queue1로 옮긴다. 횟수는 right - q1.size()이다.

그다음 queue1의 흰 칸을 모두 queue2로 옮긴다. 횟수는 left이다.

총 left + right - q1.size()이다.

 

 

 

코드

#include <string>
#include <vector>
#include <algorithm>
#define ll long long
#define INF 1e7
using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer(INF);
    ll sum(0), target(0);
    vector<int>elements(queue1.size() + queue2.size(), 0);

    for (int idx = 0; idx < queue1.size(); ++idx) {
        elements[idx] = queue1[idx];
        target += elements[idx];
    }
    for (int idx = queue1.size(); idx < queue1.size() + queue2.size(); ++idx) {
        elements[idx] = queue2[idx - queue1.size()];
        target += elements[idx];
    }

    target /= 2;

    int left(0), right(0);
    int q1_size(queue1.size()), q2_size(queue2.size());

    while (right < elements.size()) {
        if (sum < target) {
            sum += elements[right++];
        }
        else if (sum == target) {
            if (left < queue1.size() && right < queue1.size()) {
                answer = min(answer, right + q2_size + left);
            }
            else if (left < queue1.size() && right >= queue1.size()) {
                answer = min(answer, left + right - q1_size);
            }
            else if (left > queue1.size()) {
                answer = min(answer, right - q1_size + left);
            } 
            sum -= elements[left++];
        }
        else if (sum > target) {
            sum -= elements[left++];
        }
    }

    while (left < elements.size()) {
        sum -= elements[left++];
        if (sum == target) {
            answer = min(answer, left - q2_size);
        }
    }

    if (answer == INF) answer = -1;
    return answer;
}