[프로그래머스] level2 두 큐 합 같게 만들기 (java) 시간초과 해결

문제링크

 

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

프로그래머스

 

풀이 방법 (시간초과 문제 수정 전)

1. queue1, queue2에 있는 값을 모두 더한 후 2로 나눔

2. qA, qB에 queue1, queue2 각각을 넣음

3. qA와 qB의 사이즈가 0이 될때까지, qA와 qB의 합이 같은때까지 while문

4. qA의 모든 합이 qB의 모든 합보다 작다면 qB에서 한개를 빼서 qA에 넣음

    위의 조건이 아니라면(이미 같은 경우는 위에서 체크 했으므로 qA의 모든 합이 qB의 모든 합보다 크다면)

    qA에서 한개를 빼서 aB에 넣음

   

* 시간 초과가 나는 이유: 조건마다 calcSum()을 호출해서 queue에 넣었다 뺐다하기 때문

 

코드 (시간 초과)

import java.util.*;

class Solution {
    long half_sum = 0;
    
    public int solution(int[] queue1, int[] queue2) {
        int answer = -1;
        int count = 0;
        
        Queue<Integer> qA = new LinkedList<>();
        Queue<Integer> qB = new LinkedList<>();
        
        for(int i=0; i<queue1.length; i++){
            half_sum += queue1[i];
            qA.offer(queue1[i]);
        }
        for(int i=0; i<queue2.length; i++){
            half_sum += queue2[i];
            qB.offer(queue2[i]);
        }
        
        half_sum /= 2;
        
        while(qA.size() > 0 && qB.size() > 0){
            if(calcSum(qA) == half_sum){
                answer = count;
                break;
            }
            count++;
            if(calcSum(qA) < half_sum){
                qA.offer(qB.poll());
            } else {
                qB.add(qA.poll());
            }
            
        }
        
        return answer;
    }
    
    public long calcSum(Queue<Integer> q){
        long sum = 0;
        int size = q.size();
        for(int i=0; i<size; i++){
            int num = q.poll();
            sum += num;
            q.offer(num);
        }
        
        return sum;
    }
}

 

풀이 방법 (시간초과 문제 해결)

1. sumA와 sumB를 이용

2. qA와 qB에서 추가하거나 삭제할때 sumA, sumB계산

3.  qA가 queue1과 같아지는 경우 count = (queue1 + queue2) * 2

 

코드 (시간 초과 해결)

import java.util.*;

class Solution {
    
    public int solution(int[] queue1, int[] queue2) {
        int answer = -1;
        long sumA = 0, sumB = 0;
        int size = (queue1.length + queue2.length) * 2, idxA = 0, idxB = 0;
        Queue<Integer> qA = new LinkedList<>();
        Queue<Integer> qB = new LinkedList<>();
        
        for(int i=0; i<queue1.length; i++){
            sumA += queue1[i];
            qA.add(queue1[i]);
            sumB += queue2[i];
            qB.add(queue2[i]);
        }
        
        int count = 0;
        
        while(qA.size() > 0 && qB.size() > 0 && count < size){
            if(sumA < sumB){
                sumA += qB.peek();
                sumB -= qB.peek();
                qA.offer(qB.poll());
            } else if(sumA > sumB){
                sumA -= qA.peek();
                sumB += qA.peek();
                qB.offer(qA.poll());
            } else{
                answer = count;
                break;
            }

            count++;
        }
        
        return answer;
    }
}