[프로그래머스] 두 큐 합 같게 만들기 | Java

짱챌·2025년 6월 27일

투 포인터 프로그래머스

Algorithm

목록 보기

15/19

📌 문제 정보

[Lv2. 두 큐 합 같게 만들기]

💡 접근 방식

두 큐를 연결해서 하나의 배열로 합친다.

슬라이딩 윈도우처럼 합을 조절하면 된다.
sum1의 범위를 조절해서 (sum1 + sum2) / 2를 맞춰간다.

sum1 > half 이면 left++
sum1 < half 이면 right++
sum1 == half 이면 종료

right가 배열을 넘어가면 -1로 종료하면 된다.

🧪 시도한 풀이

당장 떠오른 풀이는 이거였다.
틀린 풀이는 아니었지만, 이게 정말 최선인가? 라는 의문이 있었어서
다른 풀이를 찾아보았다!


import java.util.*;

class Solution {

    public long solution(int[] queue1, int[] queue2) {

        long sum1 = Arrays.stream(queue1).sum();
        long sum2 = Arrays.stream(queue2).sum();

		long sum = sum1 + sum2;

        if (sum %2 == 1) return -1;

        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();

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

        long cnt = 0;

        while(!q1.isEmpty() && !q2.isEmpty()){
            int pop = 0;

            if (sum1 > sum2){
                pop = q1.poll();
                q2.add(pop);
                
                sum1 -= pop;
                sum2 += pop;
            } else if (sum1 < sum2){
                pop = q2.poll();
                q1.add(pop);

                sum2 -= pop;
                sum1 += pop;
            } else {
                return cnt;
            }

            cnt++;
            if (cnt >(long) queue1.length *3) return -1;
        }

        return -1;

    }
}

🔍

단순히 queue의 합이 큰 쪽에서 작은 쪽으로 옮겨가는 로직이다.
!q1.isEmpty() && !q2.isEmpty()을 while문 종료 조건으로 주어서, 한 쪽이 비게 되면 완성할 수 없다고 판단하였는데 지금 생각해보면 생략해도 될 것 같다..
queue 크기의 3배 이상 진행되면 완성할 수 없다고 판단했다. 3배가 논리적인 조건에 따른 기준은 아니었고.. 그냥 그 정도면 안되지 않을까 싶었다....

✅ 코드

import java.util.*;

class Solution {
	public int solution(int[] queue1, int[] queue2) {
      int n = queue1.length;
      int[] arr = new int[n * 2];
      long sum1 = 0, sum2 = 0;

      for (int i = 0; i < n; i++) {
          arr[i] = queue1[i];
          arr[i + n] = queue2[i];
          sum1 += queue1[i];
          sum2 += queue2[i];
      }
      
      long sum = sum1 + sum2;
      if (sum %2 == 1) return -1;
      
      long half = sum / 2;

      int left = 0, right = n;
      int count = 0;

      while (left < 2 * n && right < 2 * n) {
          if (sum1 == half) return count;

          if (sum1 > half) {
              sum1 -= arr[left];
              left++;
          } else {
              sum1 += arr[right];
              right++;
          }

          count++;

          if (count > n * 3) break;
      }

      return -1;
  }
}