[2022 카카오 인턴십 코테] 두 큐 합 같게 만들기

링크

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

 

분류

큐

그리디

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

그리디 알고리즘을 사용해야함을 떠올릴 수 있다면 매우 쉬운 문제.

문제에 큐에서 꺼낸 값은 "다른 큐"에 넣는다고 명시되어 있으므로

수의 합이 작은 큐에서 큰 큐로 원소를 넣어가며 합이 같을 때 까지 계산하면 됨.

 

큐에서 꺼낸 값을 두 큐중 아무곳에나 넣는다고 했으면 난이도가 올라갔을텐데.. 다행

 

두 큐의 최대 길이가 각각 30만 이므로 60만번 시행 후에도 큐 합이 같지 않다면 -1 리턴

(원래 두 큐 중 하나의 원소가 한번 이상 모두 꺼내졌을 때 -1을 리턴해야 하지만~ 코딩테스트니까 빠르고 간결하게)

 

시행착오

문제에 Long 타입을 고려하라고 되어있으나, 막상 문제를 풀다가 해당 내용을 깜빡해서 두 번 만에 성공

 

코드

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Integer> q1 = new LinkedList<>(), q2 = new LinkedList<>();
        long sum1 = 0, sum2 = 0;
        int cnt = 0;

        for (int i = 0; i < queue1.length; i++) {
            sum1 += (long)queue1[i];
            q1.add(queue1[i]);
        }
        for (int i = 0; i < queue2.length; i++) {
            sum2 += (long)queue2[i];
            q2.add(queue2[i]);
        }

        for (int i = 0; i <= 600000; i++) {
            if (sum1 == sum2) return cnt;
            
            if (sum1 > sum2) {
                int k = q1.poll();
                sum1 -= (long)k;
                sum2 += (long)k;
                q2.add(k);
            } else {
                int k = q2.poll();
                sum1 += (long)k;
                sum2 -= (long)k;
                q1.add(k);
            }

            cnt++;
        }

        return -1;
    }
}