문제 118667. 두 큐 합 같게 만들기

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

입력

• 길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2

입력 제한

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
• 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

입력 예제

// input
[3, 2, 7, 2]   // queue1
[4, 6, 5, 1]   // queue2

// ans
2

 

풀이 방식

우선, 두 큐의 합이 같으려면 두 큐의 들어있는 원소들의 총 합이 짝수여야한다. 따라서 총 합을 구했을 때 홀수가 나온다면 두 큐의 합이 같을 수 없으므로 -1을 리턴한다.

하나의 큐에서 pop한 값을 또 다른 큐에 push를 한다는 것을 다른 관점에서 바라보면 두 큐를 하나로 합친 큐에서 pop한 값을 다시 push하는 것과 같다. 예시로 보면 다음과 같다.

 

초기 상황

초기 상황은 다음과 같다. 입력 예제와 동일한 예이다. merge_q는 queue1과 queue2를 순서대로 합친 큐이다.

• queue1: [3, 2, 7, 2]
• queue2: [4, 6, 5, 1]
• merge_q: [ 3, 2, 7, 2, 4, 6, 5, 1 ]

queue1에서 pop, queue2에 push

queue1에서 먼저 pop하고 queue1에 push를 했다면, 다음과 같이 merge_q는 변화가 없다.

• queue1: [3, 2, 7]
• queue2: [2, 4, 6, 5, 1]
• merge_q: [ 3, 2, 7, 2, 4, 6, 5, 1 ]

queue2에서 pop, queue1에 push

반면에 queue2에서 먼저 pop하고 queue1에 push를 했다면, merge_q에서 pop하고 push했을 때와 동일한 결과가 나오게 된다.

• queue1: [1, 3, 2, 7, 2]
• queue2: [4, 6, 5]
• merge_q: [ 1, 3, 2, 7, 2, 4, 6, 5 ]

따라서, 이 문제를 풀 때 두 개의 큐가 아닌, 하나의 큐에서 push, pop하는 방식으로 관점을 바꿔 풀 수 있게된다. 문제는 일반 큐 자료구조는 인덱스로 접근할 수가 없다. 따라서, 조금 마음에 들지는 않지만 vector자료구조를 이용해 인덱스 접근을 할 수 있도록 하였다.(deque도 있지만 빨리 풀기 위해 잘 아는 자료구조인 vector를 사용했다) 

 

이제 merge_q를 반으로 갈랐을 때, 2개의 영역이 정확히 전체 원소의 합의 절반씩 되는 지를 확인하면 된다.

 

정확히 절반이 되는 경우 구하기

 

1. 순환 큐에서 부분 수열의 합을 구하는 것 처럼 부분 수열의 시작과 끝의 위치를 초기화한다.

start = 0, end = 0, sum = 3

 

2. start~end에 있는 값이 구하고자 하는 두 큐에 있는 원소들의 총합의 절반의 값(sum_tgt)보다 작으면, 크거나 같아질 때까지 end를 1증가시킨다.

(위 예제에서는 sum_tgt값이 15이다.)

start = 0, end = 1, sum = 5

start = 0, end = 2, sum = 12

start = 0, end = 3, sum = 14

 

3. sum_tgt과 값이 크거나 같아졌다면 다음 start를 1증가시킨다. sum_tgt과 값과 같은 경우엔 추가로 해당 start, end의 위치값을 pos_data라는 구조체 타입을 가지는 pos_v1변수에 값을 저장해둔다(pair자료구조를 써도 된다. 필자 pos_v1.start와 같이 가독성을 높이기 위해 구조체를 쓴 것이다. 다른 이유는 없다)

start = 0, end = 4, sum = 16, pos_v1 = [{start=0, end=4}]

 

4. 모든 경우의 수를 구할 때까지 2~3 과정을 반복한다.

 

필요한 작업의 최소 횟수 구하기

이제 절반이 될 수 있는 모든 경우의 수가 pos_v1이라는 변수에 start, end값으로 저장되어 있다. 이제 이 start, end값을 활용해 필요한 작업의 최소 횟수를 구해야한다. 최소 횟수를 구하는 법은 아주 간단한데 for문으로 pos_v1를 순회할 때마다 각각의 start와 end값을 통해 pop, push의 작업 횟수를 구하고, 이전까지 구한 작업 횟수랑 비교해서 작은 값을 정답으로 저장하면 된다.

 

start, end를 통해 pop, push의 작업 횟수를 구하는 방법은 아래와 같다.(이유는 따로 설명하지 않겠다)

int pop_cnt = pd.start;
int push_cnt = pd.end < queue1.size() ? 0 : pd.end + 1 - queue1.size();

// queue1에서 시작한 연속된 부분 수열이 queue1의 끝부분 일부를 포함하지 않는다면, 
// 수열을 queue2에 넘기고 queue2원소를 전부 queue1로 넘겨야한다.
if(pd.end < queue1.size() - 1){
    pop_cnt = pd.end + 1;
    push_cnt = queue2.size();
}

 

결과적으로 pos_v1를 for문으로 순회하는 작업이 끝나면 정답이 나오게 된다!

정답 코드 

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

struct pos_data{
    int start;
    int end;
};

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = INT_MAX;
    long long q_sum1 = 0, q_sum2 = 0;
    
    vector<int> merge_q;
    
    for(int elem1 : queue1){
        q_sum1 += elem1;
        merge_q.push_back(elem1);
    } 
    for(int elem2 : queue2){
        q_sum2 += elem2;
        merge_q.push_back(elem2);
    } 
    
    int start = 0, end = 0;
    long long sum = merge_q[0], sum_tgt = (q_sum1 + q_sum2) / 2;
    
    // 두 큐의 합이 홀수이면 -1.
    if((q_sum1 + q_sum2) % 2) return -1;
    
    vector<pos_data> pos_v1;
    do{
        
        if(sum < sum_tgt){
            end++;
            sum += merge_q[end];
        }
        else if(sum >= sum_tgt){    
            if(sum == sum_tgt){
                pos_v1.push_back({start, end});
            }
            
            sum -= merge_q[start];
            start++;
        }
        
    }
    while(start <= end && end < merge_q.size());
    
    // 큐의 합을 같게 만들 수 있는 경우를 찾지 못한 경우 -1
    if(pos_v1.size() == 0) return -1;
    
    for(pos_data pd : pos_v1){
    
        int pop_cnt = pd.start;
        int push_cnt = pd.end < queue1.size() ? 0 : pd.end + 1 - queue1.size();
        
        // queue1에서 시작한 연속된 부분 수열이 queue1의 끝부분 일부를 포함하지 않는다면, 
        // 수열을 queue2에 넘기고 queue2원소를 전부 queue1로 넘겨야한다.
        if(pd.end < queue1.size() - 1){
            pop_cnt = pd.end + 1;
            push_cnt = queue2.size();
        }
        
        answer = min(answer, pop_cnt + push_cnt);
    
    }
    
    return answer;
}