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

🚨 실패 코드

• 각 배열을 각각 큐에 넣고, 합계도 구하기
• queue1의 합이 queue2의 합보다 더 작으면 queue2에서 꺼내서 queue1에 넣기
• 반대로 queue2도 더 작으면 queue1 원소 넣기
• 큐에서 넣을때 해당 큐에 원소가 하나밖에 없으면 같은 합을 못 만드므로 -1 리턴
  🫥 테스트케이스 30개중 5개 시간초과

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        int sum1 = 0;
        int sum2 = 0;
        int total = sum1 + sum2;
        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]);
        }
        
        while(sum1 != sum2){
            if (sum1 < sum2){
                if (q2.size() == 1) return -1;
                int n = q2.poll();
                sum1 += n;
                sum2 -= n;
                q1.add(n);
            } else {
                if (q1.size() == 1) return -1;
                int n = q1.poll();
                sum2 += n;
                sum1 -= n;
                q2.add(n);
            }
            answer++;
        }
        
        
        return answer;
    }

}

💡 풀이

• queue2 원소 합은 굳이 필요 없이 queue1 원소 합이랑 total 원소 합 구하기
• 위 코드에서 실패했던 이유는 다 순회해서 결국 처음 큐의 원소와 같아졌으면 더이상 반복할 필요 없어서 return -1
• queue1.length 4는 (queue1.length + queue2.length) 2를 의미

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        long sum1 = 0;
        long total = 0;
        Queue<Integer> q1 = new LinkedList<>(); 
        Queue<Integer> q2 = new LinkedList<>();
        for(int i = 0; i<queue1.length; i++){
            sum1 += queue1[i];
            total += queue1[i] + queue2[i];
            
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }
        
        while(sum1 != total/2){
        	// 다 순회하고 결국 다시 원래 자리로 오면 return
            if (answer > queue1.length * 4) return -1;
            
            if (sum1 < total/2){
                if (q2.size() == 1) return -1;
                int n = q2.poll();
                sum1 += n;
                q1.add(n);
            } else {
                if (q1.size() == 1) return -1;
                int n = q1.poll();
                sum1 -= n;
                q2.add(n);
            }
            answer++;
            
           
        }
        
        
        return answer;
    }

}