[구현] 프로그래머스 두 큐 합 같게 만들기 (실패분석 - 아이디어)

접근

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

이 문제는 아이디어를 제대로 떠올리지 못했습니다.

다른 스터디원의 풀이를 보면서
제가 너무 문제를 어렵게 접근하는 경향이 있다는 것을 깨달을 때가 많습니다.

뭔가 카카오 문제처럼 조건이 많은 문제를
하나하나 만족시키면서 구현하는 것이 재미있는데
위 문제처럼 어떤 규칙을 발견하는 구현 문제가 약한거 같습니다.

일단 저의 어렵고 긴 풀이에 대해서 설명해보려고 합니다.
저는 아래와 같이 접근했습니다.

1. 두 개의 배열을 이어 붙인다.
2. 이어 붙이는 방법은 두 가지이다.

int[] newArray = new int[queue1.length + queue2.length];

 System.arraycopy(queue1, 0, newArray, 0, queue1.length);
 System.arraycopy(queue2, 0, newArray, queue1.length, queue2.length);

2-1 queue1+queue2 = 3, 2, 7, 2, 4, 6, 5, 1
2-2 queue2+queue1 = 4, 6, 5, 1, 3, 2, 7, 2
3. 그러면 위와 같이 15를 만드는 배열을 발견할 수 있다.
4. 2,7,2,4를 만들기 위한 횟수와 1,3,2,7,2를 만들 수 있는 횟수를 비교하여
최소 횟수가 답이 된다.

그러나 4번에서 어떻게 저 부분을 구현해야 하나 생각하다가 시간이 부족하여 풀지 못했습니다.

따라서 더 간단한 방법의 풀이를 참고하였습니다.

방법은 간단합니다.
주어진 두개의 queue의 합이 더 작은쪽은 합이 더 큰 큐 쪽에서 값을 가지고 옵니다.
이걸 반복해서 하지만 그 횟수가 두 큐의 길이의 합보다 큰 경우에는 두 큐의 합을 같게 만들 수 없는 경우이기 때문에 그만하고 -1을 반환합니다.
(ex 100과 1,1,1,1)

틀린 풀이

import java.util.*;

class Solution {
    
    static Queue<Integer> q1 ;
    static Queue<Integer> q2 ;
    
    
    public int solution(int[] queue1, int[] queue2) {
        int answer = -1;
        
        // 두 수의 합이 2로 나눠지는가?    
        
        long sum1 =0;
        long sum2 =0;
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
        
  
        for(int i=0;i<queue1.length;i++){
            sum1+=queue1[i];
            sum2+=queue2[i];
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }
        
        //홀수이면 일단 -1 return
        if((sum1+sum2)%2==1){
            return -1;
        }
        
        long tSum = (sum1+sum2)/2;
        
        int cnt1 = check(queue1,queue2,tSum);
        int cnt2 = check(queue2,queue1,tSum);
        
        System.out.println("cnt1:"+cnt1);
        System.out.println("cnt2:"+cnt2);
        
        
      

        
        return answer;
    }
    
    static int check(int[] queue1, int[] queue2, long tSum){
        
        int min=Integer.MAX_VALUE;
        
        int[] newArray = new int[queue1.length + queue2.length];

         System.arraycopy(queue1, 0, newArray, 0, queue1.length);
         System.arraycopy(queue2, 0, newArray, queue1.length, queue2.length);
        
        
        int r=0;
        int l=0;
        long sum=newArray[0];
        boolean tag = false;
        
        //여기 투포인터에서 문제
        while(true){
            //System.out.println(sum);
            if(l==newArray.length-1 && r==newArray.length-1) break;
            
            if(sum>tSum){
                sum-=newArray[l];
                if(l+1<newArray.length) l++;
            }else if(sum<tSum){
                if(r+1<newArray.length) 
                    r++;
                sum+=newArray[r];
            }else {
                tag=true;
                int result = makeArray(l,r,newArray);
                if(result<min) min=result;
                sum-=newArray[l];
                if(l+1<newArray.length) l++;
            }
        }
        if(!tag) return -1;
        
        return min;
        
    }
    static int makeArray(int l, int r, int[] newArray){
       
       int cnt=0;
        
        for(int i=l;i<=r;i++){
            System.out.println(newArray[i]);
        }
        
         
        for(int i=l;i<=r;i++){
            if(q1.contains(newArray[i])){
                int size = q1.size();
                for(int j=0;j<size;j++){
                    if(q1.peek()==newArray[i]) {
                        cnt++;
                        q1.poll();
                        break;
                    }else{
                        cnt++;
                        q2.offer(q1.poll());
                    }
                }
            }else {
                int size = q2.size();
                for(int j=0;j<size;j++){
                    if(q2.peek()==newArray[i]) {
                        cnt++;
                        q2.poll();
                        break;
                    }else{
                        cnt++;
                        q1.offer(q2.poll());
                    }
                }
            }
             
        }
        
        return cnt;
        
    }
    

}

올바른 풀이

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
   
        int answer=0;
        long sum1=0;
        long sum2=0;
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        for(int i=0;i<queue1.length;i++){
            sum1+=queue1[i];
            sum2+=queue2[i];
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }
        
        if((sum1+sum2)%2!=0) return -1;
        
        int max_num = queue1.length*2; // 큐의 모든 삽입을 진행할 경우
        int cnt1 = 0; // queue1의 삽입 횟수
        int cnt2 = 0; // queue2의 삽입 횟수
        
        while(true){
            
            
            //1. 같은 경우
            if(sum1==sum2) break;
            
            //2. 모두 다 돌았지만 없는 경우
            if(cnt1 > max_num || cnt2 > max_num) return -1;
            
            //3. 비교를 통하여 추출과 삽입
            // 3-1 : queue1의 합이 queue2보다 작은 경우 queue2에서 추출하여 queue1에 삽입
            if(sum1<sum2){
                sum2-=q2.peek(); 
                sum1+=q2.peek();
                cnt1++;
                q1.add(q2.poll());
                answer++;
                
            // 3-2 : queue2의 합이 queue1보다 작은 경우 queue1에서 추출하여 queue2에 삽입    
            }else if(sum2<sum1){
                sum1-=q1.peek();
                sum2+=q1.peek();
                cnt2++;
                q2.add(q1.poll());
                answer++;
            }
            
        }
        
        
        
        
        return answer;
    }
}