프로그래머스 두 큐 합 같게 만들기 | 자바

2022 카카오 테크 인턴십

 

📌 알고리즘 선택

별다른 알고리즘은 없고, 구현 문제라고 생각한다.

 

---

📌 풀이

정직하게 큐의 사이즈만큼 반복해서 풀이하면 시간초과가 난다. 그렇기에 조금 다르게 접근할 필요가 있다.

한쪽 큐의 합을 (두 큐의 합 / 2)로 만들어주면 어떨까?

 

한쪽 큐의 합이

(초기의 두 큐의 합 / 2)보다 크면 poll하여 다른 큐에 add 해주고,

작으면 다른 큐에서 poll 하여 한쪽 큐에 add 해주면 된다.

 

반복문은 한쪽 큐의 합과 (초기의 두 큐의 합 / 2)이 같아질 때까지 반복하면 되는데,

어떤 방식으로도 두 큐의 합을 같게 만들 수 없는 경우가 있을 수 있기에, 초기의 한쪽 큐의 길이의 3배 만큼 반복문을 반복해주고, 그래도 두 큐의 합이 같지 않다면 -1을 리턴해주자.

 

여기서, 왜 3배일까?

대강 최악의 경우를 생각해보면, 큐1과 큐2의 값들을 서로 전부 교환하는 경우인데 이때 대략 큐의 길이의 2배 만큼 반복하게 된다. 따라서 큐의 길이의 3배 만큼 반복해준다면, 예외 상황도 없고 시간 초과도 나지 않을 것이다.

 

---

📌 코드

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = -2;
        
        Queue<Integer> que1 = new LinkedList<>();
        Queue<Integer> que2 = new LinkedList<>();
        
        long total = 0; // 두 큐에 담긴 수들의 합 / 2
        long hap = 0; // 큐1의 합을 실시간으로 저장할 변수
        
        for(int i = 0; i < queue1.length; i++) {
            total += queue1[i];
            hap += queue1[i];
            total += queue2[i];
            que1.add(queue1[i]);
            que2.add(queue2[i]);
        }
        
        int maxCount = queue1.length * 3;
        total /= 2; // 하나의 큐의 합이 전체/2와 같으면 됨
        
        while(hap != total) {
            // 어떤 경우에도 각 큐의 원소 합을 같게 만들 수 없을 때
            if(maxCount == 0)
                return -1;
            
            // 큐1의 합이 큐2의 합보다 클 때
            if(hap > total) {
                int temp1 = que1.poll();
                hap -= temp1;
                que2.add(temp1);
            }
            // 큐1의 합이 큐2의 합보다 작을 때
            else {
                int temp2 = que2.poll();
                hap += temp2;
                que1.add(temp2);
            }
            
            maxCount--;
        }
        
        
        return queue1.length * 3 - maxCount;
    }
    
}

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

프로그래머스