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

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

프로그래머스

<풀이>

1. 두 개의 큐를 입력받는다.

2. 두 개의 큐의 원소의 합이 같아질 때까지 원소를 이동한다.

3. 원소이동작업의 최소회수를 반환한다.

 

<해법>

1. 원소이동을 최소로 하는 방법

=> 작업회수를 최소로 하는 방법부터 생각해야합니다. 최소로 하는 방법은 작업때 마다 원소의 합이 큰 큐에서 원소를 빼서 작은 쪽으로 넣는 방법입니다. 이유는 큰 쪽에서 작은 쪽으로 넘겨야 작업 회수가 최소가 되기 때문입니다. 물론, 작은 쪽에서 먼저 빼고, 큰 쪽에서 빼는 경우가 최소회수가 될 수도 있습니다. 하지만, 이 경우는 큰 쪽에서 먼저 빼는 경우와 회수가 같은 경우일 뿐입니다. 이 부분은 직접 그림을 그려가며 해보시면 충분히 이해하실 수 있습니다.

 

2. 원소이동 방법

=> 주어진 벡터에서 포인터를 이용해서 원소이동을 구현합니다. 아래 그림과 코드를 참고해서 봐주시면 이해하실 수 있습니다.

 

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
int solution(vector<int> queue1, vector<int> queue2) {
 
    //선언
    int answer;                         //-> 정답
    vector<int>::iterator ptr1, ptr2;   //-> 큐 포인터
    long long sum_all, sum1, sum2;      //-> 큐1+큐2합, 큐1합, 큐2합
 
    //초기화
    answer = 0;
    ptr1 = queue1.begin(), ptr2 = queue2.begin();
    sum_all = 0, sum1 = 0, sum2 = 0;
 
    /* 해법 */
    //1. 큐1, 큐2, 큐1+큐2 원소 합 구하기
    for (int i = 0; i < queue1.size(); i++) {
        sum1 += queue1[i];
        sum2 += queue2[i];
    }
    sum_all = sum1 + sum2;
 
    //2. 큐1+큐2 원소 합이 홀수일 경우 -> 불가능
    if (sum_all % 2 != 0) {
        answer = -1;
    }
    else {
        //3. 큐1, 큐2에 있는 두 개의 포인터를 조종하며 원소 합 구하기
        while (true) {
 
            //종료조건1 -> 두 큐의 합이 같을 경우
            if (sum1 == sum2) {
                break;
            }
 
            //종료조건2 -> 포인터1이 큐2 끝까지 갔을 경우 or 포인터2가 큐1 끝까지 갔을 경우(탐색완료)
            if (ptr1 == queue2.end() || ptr1 == queue1.end()) {
                answer = -1;
                break;
            }
 
            //큐의 포인터 옮기기
            if (sum1 > sum2) {
                sum1 -= *ptr1;
                sum2 += *ptr1;
                
                ptr1++;
                if (ptr1 == queue1.end()) {
                    ptr1 = queue2.begin();
                }
            }
            else {
                sum2 -= *ptr2;
                sum1 += *ptr2;
                
                ptr2++;
                if (ptr2 == queue2.end()) {
                    ptr2 = queue1.begin();
                }
            }
 
            answer++;
        }
    }
 
    //반환
    return answer;
}

 

구현에 대해 알아볼 수 있는 문제였습니다.