프로그래머스 두 큐 합 같게 만들기 python, java

그리디한 방법으로 접근한다. 목표값을 기준으로 지금 보고 있는 큐의 원소 합이 작으면 추가하고 크면 뺀다.

📜 문제 바로 가기 : 두 큐 합 같게 만들기

제출코드

파이썬

from collections import deque

def solution(q1, q2):
    target = (sum(q1) + sum(q2)) // 2
    length = len(q1) * 3
    dq1, dq2 = deque(q1), deque(q2)

    cnt = 0
    v = sum(q1)
    while cnt <= length and v != target:
        cnt += 1
        if target < v:
            a = dq1.popleft()
            dq2.append(a)
            v -= a
        elif target > v:
            a = dq2.popleft()
            dq1.append(a)
            v += a
    
    if cnt > length:
        cnt = -1
    
    return cnt

자바

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Deque<Long> dq1 = new LinkedList<>();
        Deque<Long> dq2 = new LinkedList<>();
        
        long target = 0;
        long v = 0;
        for (int i = 0; i < queue1.length; i++) {
            target += (Long.valueOf(queue1[i]) + Long.valueOf(queue2[i]));
            v += Long.valueOf(queue1[i]);
            dq1.add(Long.valueOf(queue1[i]));
            dq2.add(Long.valueOf(queue2[i]));
        }
        
        target /= 2;
        int maxCnt = queue1.length * 3;
        int cnt = 0;
        while (cnt <= maxCnt && v != target) {
            cnt += 1;
            
            if (v < target) {
                long a = dq2.pollFirst();
                dq1.add(a);
                v += a;
            } else {
                long a = dq1.pollFirst();
                dq2.add(a);
                v -= a;
            }
        }
        
        int answer = -1;
        if (cnt <= maxCnt) {
            answer = cnt;
        }
        return answer;
    }
}

---

접근방법

deque를 이용해서 queue를 구현했다. 목표값이 두 큐의 합의 절반이기 때문에 둘 중 하나의 큐만 체크하면 된다. 큐에 값을 더하고 빼는 것은 그리디한 방법으로 접근하면 되는데 절대 만들어질 수 없는 경우 어디까지 확인을 해야될지가 문제였다.

처음에는 두 큐원소가 전체다 나왔다가 다시 들어가면 모든 경우를 봤다고 해도 될거 같아서 처음 큐길이의 2배로 잡았는데 이는 모든 경우를 다 잡을 수 없었다.

예를들어 [1, 1, 7, 1], [1, 1, 1, 1] 의 경우 1번 큐에서 7까지 모두 뺐다가 다시 2번큐에서 7을 제외한 모든 값을 빼야되기때문에 큐길이의 2배이상 연산이 필요하다.

따라서 여유있게 3배로 주고 문제를 풀었다. 처음 큐의 길이가 30만이기 때문에 3배를 줘도 시간에 여유가 있다.