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

프로그래머스 두 큐 합 같게 만들기 [2022 KAKAO TECH INTERNSHIP]
https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

문제 풀이

• 이 문제는 투 포인터 알고리즘을 사용하여 해결했습니다.
• 다음 사진과 같이, 큐를 사용하지 않고 두 개의 배열을 합친 후 각 배열의 시작과 끝을 가리키는 투 포인터를 두어 배열을 구분 짓도록 합니다. 

• 다음으로 두 배열의 합을 같게 하기 위해 배열의 합이 큰 배열에서 작은 배열로 값을 넘겨줍니다. (합이 큰 배열 - 맨 앞의 값 pop, 합이 작은 배열 - 맨 뒤에 값 push) 해당 과정을 그림으로 보면 다음과 같습니다.

• 1번 배열의 합은 14, 2번 배열의 합은 16이었기 때문에 2번 배열에서 1번 배열으로배열로 값을 넘겨줍니다. 배열의 맨 앞의 값을 넘겨주어야 하기 때문에 2번 배열의 시작 포인터의 인덱스를 하나 증가시키고, 1번 배열의 종료 포인터의 인덱스를 하나 증가시킴으로 2번 배열에서 1번 배열로 값을 넘겨주게 됩니다.
• 이제 각 배열의 합은 1번 배열 : 18, 2번 배열 : 12가 되었습니다. 위의 과정을 반복하여 이번에는 1번 배열에서 2번 배열로 값을 넘겨줍니다.

• 1번 배열에서 2번 배열로 값을 넘겨주게 되면 배열과 포인터의 상태는 위와 같게 되고 두 배열의 합이 같아지게 됩니다. 문제를 해결하기 위해 위의 과정을 반복하여 두 배열의 합을 같게 하는 최적의 횟수를 찾으면 됩니다.
• 마지막으로 배열의 합을 같게 만들 수 없다면 -1을 리턴해야 합니다. 한 사이클이 돌아 배열과 포인터의 상태가 처음과 같아졌음에도 합을 같게 만들지 못했다면, 합을 같게 만들 수 없는 경우로 간주합니다.

• 배열과 포인터의 상태가 위와 같이 되었을 때 처음 상태와 같다고 판단할 수 있는데, 이는 각 포인터가 S(한 배열의 길이)씩 움직여 총 4S 만큼 움직였을 때 입니다. 그러므로 이동 횟수가 4S가 넘어간다면 반복 과정을 종료시키고 -1을 리턴합니다.

코드

#include <string>
#include <vector>
#include <numeric>

using namespace std;

int S;

int addIndex(int idx) {
    return idx + 1 >= 2*S ? 0 : idx + 1; // 인덱스가 배열의 크기 넘어가면 맨 앞으로
}

int solution(vector<int> queue1, vector<int> queue2) {
    long long sum1 = accumulate(queue1.begin(), queue1.end(), 0LL);
    long long sum2 = accumulate(queue2.begin(), queue2.end(), 0LL);
    
    S = queue1.size();
    int answer = 0;
    
    // 두 배열 concat
    queue1.insert(queue1.end(), queue2.begin(), queue2.end());
    int p1_1 = 0, p1_2 = S-1;
    int p2_1 = S, p2_2 = 2*S - 1;
    
    while(answer <= 4*S) { // 이동 횟수 4S 넘어가면 종료
        if(sum1 > sum2) {
            sum1 -= queue1[p1_1];
            sum2 += queue1[p1_1];
            
            p1_1 = addIndex(p1_1);
            p2_2 = addIndex(p2_2);
        }
        else if(sum1 < sum2) {
            sum2 -= queue1[p2_1];
            sum1 += queue1[p2_1];
            
            p2_1 = addIndex(p2_1);
            p1_2 = addIndex(p1_2);
        }
        else return answer;
        
        answer++;
    }
    
    return -1;
}

실행 결과