두 큐 합 같게 만들기 (Programmers Lv.2)

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

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

프로그래머스

 

문제를 딱 보고 든 생각으로 첫 번째는 재귀.
하지만 사이즈를 재보면 시간초과가 뻔해서 패스하고...

 

두 번째로 든 생각은 루프를 돌려서 값을 추려낸다?
뭔가 될 법도 해서 시도해보았다...

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = -1;
    
    int cnt=0, maxleng=queue1.size()+queue2.size(), tmp=-1;
    
    long long sum1=0, sumTarget=0;
    for(auto q: queue1)
        sumTarget += q;
    for(auto q: queue2)
        sumTarget += q;
    
    while(1){
        sum1=0;
        for(auto q: queue1)
            sum1 += q;
        
        if(sum1 == sumTarget/2){
            answer = cnt;
            break;
        }
        
        if(queue1.size() == maxleng || queue2.size() == maxleng)
            break;
        
        if(sum1 > sumTarget-sum1){
            tmp = queue1[0];
            queue1.erase(queue1.begin());
            queue2.push_back(tmp);
            cnt++;
        }
        else if(sum1 < sumTarget-sum1){
            tmp = queue2[0];
            queue2.erase(queue2.begin());
            queue1.push_back(tmp);
            cnt++;
        }
    }
    
    return answer;
}

 

결과는... testcase가 5개나 나가버렸다!!! 😂😂😂

 

눈물을 머금고 문제를 다시 살펴보았다.

음... 뭐가 있을까 고민하다...

 

'queue1과 queue2에 인덱스를 설정해볼까?' 라는 생각이 들었다. (솔직히 자신은 없었지만...)

 

...
int s1=0, s2=0, e1=queue1.size(), e2=queue2.size();
...
while(cnt <= maxleng){
    if(sum1<sum2){
        sum2 -= queue2[s2];
        sum1 += queue2[s2++];

        if(s2 == e2)
            s2=0;
    }
    else if(sum2<sum1){
        sum1 -= queue1[s1];
        sum2 += queue1[s1++];

        if(s1 == e1)
            s1=0;
    }
    ...

 

첫 시도는 실패.

 

인덱스를 따로 잡아서 각각 돌리려 했는데 해당 알고리즘을 머리로 굴려봐도 이상했다.

그럼 어떻게 해야할까...?

 

C++ 풀이)

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = -1;
    
    int cnt=0, maxLeng=queue1.size()+queue2.size();
    
    vector<int> total_queue;
    long long sum1=0, sum2=0;
    for(auto q: queue1){
        sum1 += q;
        total_queue.push_back(q);
    }
    for(auto q: queue2){
        sum2 += q;
        total_queue.push_back(q);
    }
    
    int s1=0, e1=queue1.size()-1, s2=queue1.size(), e2=maxLeng-1;
    while(cnt <= maxLeng*2){
        if(sum1<sum2){
            sum2 -= total_queue[s2++ % maxLeng];
            sum1 += total_queue[++e1 % maxLeng];
        }
        else if(sum2<sum1){
            sum1 -= total_queue[s1++ % maxLeng];
            sum2 += total_queue[++e2 % maxLeng];
        }
        else{
            answer = cnt;
            break;
        }
        
        cnt++;
    }
    
    return answer;
}

 

total_queue를 만들어 queue1 과 queue2 의 원소를 다 집어놓고 인덱스를 설정했다.

 

결과는 성공!!! (사실 엄청 틀렸다...)

 

여기서 키포인트는 바로 cnt <= maxLeng*2 였다.

queue1 과 queue2 모두 탐색할 수 있는 범위를 설정해줘야 최악의 경우도 계산이 가능하다.

 

그럼 이를 내가 공부하고 있는 자바스크립트(JS)로 풀어보자.

 

JS 풀이)

function solution(queue1, queue2) {
    let answer = -1;
    
    let cnt=0, maxLeng=queue1.length+queue2.length;
    let total_queue = [...queue1, ...queue2];
    let sum1=0, sum2=0;
    queue1.forEach((num) => sum1 += num);
    queue2.forEach((num) => sum2 += num);

    let s1=0, e1=queue1.length-1, s2=queue1.length, e2=maxLeng-1;
    while(cnt <= maxLeng*2){
        if(sum1<sum2){
            sum2 -= total_queue[s2++ % maxLeng];
            sum1 += total_queue[++e1 % maxLeng];
        }
        else if(sum2<sum1){
            sum1 -= total_queue[s1++ % maxLeng];
            sum2 += total_queue[++e2 % maxLeng];  
        }
        else{
            answer = cnt;
            break;
        }
        
        cnt++;
    }
    
    return answer;
}

 

아직 쌩 자바스크립트 문법만으로 Lv.2를 풀기엔 모자란 듯 하다...

 

요즘 계속해서 LV.2를 풀고 있는데, 생각보다 막히는 부분이 많다.
아무래도 기본기가 부족한 탓이겠지... 더욱 신경써서 공부하자!!!