코딩테스트 -- 두 큐 합 같게 만들기 - (프로그래머스 / C++)

 

프로그래머스

 

문제!

---

 

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert 하면[2, 3, 4, 5]가 됩니다.

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

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

---

요약하면 두 큐에 있는 값들을 적절히 pop push 하여 서로 가지고 있는 값의 합이 같게 되도록 하는 최소의 작업 횟수를 찾는 문제입니다.

 

 

물론 그냥 queue로 구현을 하면 될 것 같지만 한번 다르게 생각해보았습니다

 

어차피 들어가는 곳은 뒤, 나오는 곳은 앞으로 정해져 있다면     

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

  숫자 배열은 3 2 7 2 4 6 5 1로 정해져 있습니다.

 

이 숫자들의 총합은 30!

 

누적합을 통해 15가 나오는 구간을 찾아준다면? 반대쪽은 자연스레 15가 나올 테니

얼마나 작업을 시행했는지만 구하면 끝!

 

 

 

하지만 역시 틀려버렸습니다...

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> all_list;


int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 987654321;
    
    int sum=0;
    int memo=0;
    
    for(int i=0;i<queue1.size();i++){
        sum+=queue1[i];
        all_list.push_back(sum);
    }
    
    for(int i=0;i<queue2.size();i++){
         sum+=queue2[i];
        all_list.push_back(sum);
    }
    if(sum%2!=0){
        return -1;
    }
    
    sum=sum/2;
    
    
    for(int i=0;i<all_list.size();i++){//범위 시작
        for(int j=i+1;j<all_list.size();j++){//끝
            if(all_list[j]-all_list[i]>sum){
                break;
            }
            else if(all_list[j]-all_list[i]==sum){
                memo=i+(j-queue1.size()+2);
                answer=min(answer,memo);
                break;
            }
        }
    }
    
    if(answer==987654321){
        return -1;
    }
    

    return answer;
}

방법은 맞는 것 같은데..... 작업수를 세어주는 방식이 틀린 걸까요...

 

 

 

일단  다음 방법!

 

 

 

 

그냥 queue구현....

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
  long long sum = 0, sum2 = 0;
  queue<int> q, q2;
    
  for (int num : queue1) {
      sum += num;
      q.push(num);
  }
    
  for (int num : queue2) {
      sum2 += num;
      q2.push(num);
  }
    
  int idx = 0, idx2 = 0;
  int maxIdx = queue1.size()*2;
  int answer = 0;
  
  while (idx < maxIdx && idx2 < maxIdx){
      if (sum == sum2){
          return answer;
      }
      answer++;
      if (sum < sum2){
          int cur = q2.front();
          q2.pop();
          q.push(cur);
          sum += cur;
          sum2 -= cur;
          idx2++;
      }
      else{
          int cur = q.front();
          q.pop();
          q2.push(cur);
          sum2 += cur;
          sum -= cur;
          idx++;

      }
  }
  return -1;
}

 

이렇게 쉽게 되네요... 

 

계속 이동시켜주면서 두 쪽의 값 차이를 낮춰주는 방법입니다.

 

이렇게 쉽게 되네요

 

 

 

 

 

 

ALL

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
  long long sum = 0, sum2 = 0;
  queue<int> q, q2;
    
  for (int num : queue1) {
      sum += num;
      q.push(num);
  }
    
  for (int num : queue2) {
      sum2 += num;
      q2.push(num);
  }
    
  int idx = 0, idx2 = 0;
  int maxIdx = queue1.size()*2;
  int answer = 0;
  
  while (idx < maxIdx && idx2 < maxIdx){
      if (sum == sum2){
          return answer;
      }
      answer++;
      if (sum < sum2){
          int cur = q2.front();
          q2.pop();
          q.push(cur);
          sum += cur;
          sum2 -= cur;
          idx2++;
      }
      else{
          int cur = q.front();
          q.pop();
          q2.push(cur);
          sum2 += cur;
          sum -= cur;
          idx++;

      }
  }
  return -1;
}

 

 

 

****제 방법은 지금 계산 방식이 잘못되었습니다...

받아오는 건 괜찮은데 주는 부분에서 좀 더 추가되야할 게 있는 것 같습니다.

 

----- 추가 ------ 

이 방법에 대해 여러번 시도를 해보고 

 

다시 코드를 작성해 보았지만

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> all_list;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 987654321;
    
    int sum=0;
    int memo=0;
    
    for(int i=0;i<queue1.size();i++){
        sum+=queue1[i];
        all_list.push_back(sum);
    }
    
    for(int i=0;i<queue2.size();i++){
        sum+=queue2[i];
        all_list.push_back(sum);
    }
    
    if(sum%2==1){
        return -1;
    }
    
    int target=sum/2;
    
    int point1=0;
    int point2=0;
    
    
    
    for(int i=0;i<all_list.size();i++){//부분합
        for(int j=i+1;j<all_list.size();j++){
            
            if(all_list[j]-all_list[i]>sum){
                break;
            }

            
            if(all_list[j]-all_list[i]==target){// i+1~ j 까지의 합이 절반임
                point1=i+1;
                point2=j;
                int standar=queue1.size()-1; // 인덱스
                
                if(point2<standar){//첫번째에서끝남
                    answer=min(answer,point1+standar-point2); 
                }
                else if(point2>standar and point1<standar){// 반반
                    answer=min(answer,point1+point2-standar); 
                }
                else{//두번째에서
                    answer=min(answer,point1-standar+point2-standar); 
                }
            }
            
        }
    }
    
    if(answer==987654321){
        return -1;
    }
    
    

    return answer;
}

합을 계산할순있지만 모든 경우를 보진 않는 것 같습니다.

 

당장 예시인

[1, 2, 1, 2]

[1, 10, 1, 2]

 만 봐도 저의 코드에서는 121212를 만들어 내지 못합니다.....

 

그렇기에 큐로 푸는것이 가장 바른 방법인것 같습니다!

 

 

 

 

 

틀린 점이 있다면 댓 달아주세요!