29. Programmers Lv 2. '두 큐 합 같게 만들기(2022 Kakao Tech Internship)'

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

프로그래머스

두 큐의 합을 같게 만드는 방법에 대해서 여러가지로 고민을 했다.

처음에는 조합을 생각했는데.. 가능한 경우의 수가 너무 많고, 루프가 끝나지도 않을것 같았다. 적절한 리턴조건도 생각나지 않았다.

그러던 중 더 큰쪽에서 작은쪽으로 큐의 값을 하나씩 넘기다 보면 되지 않을까? 하는 생각이 들었다.

스택이라면 무한반복이 될 수도 있겠지만, 큐라서 가능할 것 같았다. 구상한대로 코드를 짠 결과, 샘플 예시는 모두 통과하였다!

그런데 최적화가 필요해서 나머지 테스트 케이스가 틀린거라고 판단했다.

기존 함수들을 모두 지우고 queue.peek()을 활용해서 더하고 빼는 역할을 대신 하도록 했다.

결과는 통과!!

 

import java.util.*;

class Solution {
    static int rnd = 0;
    static long total = 0;
    static Queue<Integer> q1 = new LinkedList<>();
    static Queue<Integer> q2 = new LinkedList<>();
    static long cnt1 = 0, cnt2 = 0;
    
    public int solution(int[] queue1, int[] queue2) {
        int num = 0;
        for (int i : queue1) {
            q1.offer(i);
            cnt1 += i;
            total += i;
            num++;
        }
        for (int i : queue2) {
            q2.offer(i);
            cnt2 += i;
            total += i;
            num++;
        } // 모든 합을 계산
          // 모든 합이 홀수이면 답 없음 => -1 리턴
        if (total % 2 == 1)
            return -1;

        boolean hasAnswer = true;
        // 큐의 합이 더 적은쪽에서 받기
        while (cnt1 != cnt2) { // 두 큐가 같지 않을 때
            if (rnd > num *2 ) {
                hasAnswer = false;
                break;
            }
            if (cnt1 > cnt2) {
                send(q1, q2, true); // send / receive
            } else {
                send(q2, q1, false);
            }
        }
        if (!hasAnswer) {
            return -1;
        } else {
            return rnd;
        }
    }
    public static void send(Queue<Integer> send, Queue<Integer> receive, boolean q1Send) {
        long sendVal = send.peek();
        if (q1Send) {
            cnt1 -= sendVal;
            cnt2 += sendVal;
        } else {
            cnt2 -= sendVal;
            cnt1 += sendVal;
        }
        rnd++;
        receive.add(send.poll());
    }
}