이번에 풀어본 문제는
프로그래머스 두 큐 합 같게 만들기 입니다.
import java.util.*;
class Solution {
public int solution(int[] queue1, int[] queue2) {
Queue<Integer> leftQ = new LinkedList<>();
Queue<Integer> rightQ = new LinkedList<>();
long sumLeft = 0, sumRight = 0;
for (int n : queue1) {
leftQ.add(n);
sumLeft += n;
}
for (int n : queue2) {
rightQ.add(n);
sumRight += n;
}
long sum = sumLeft + sumRight;
// 홀수면 무조건 불가능
if (sum % 2 != 0) return -1;
int limit = leftQ.size() * 2;
sum /= 2; // 최종 결괏값
int left = 0, right = 0;
while(left <= limit && right <= limit) {
if (sumLeft == sum) return left + right;
if (sumLeft > sum) {
// 왼쪽이 크면
int tmp = leftQ.poll();
sumLeft -= tmp;
sumRight += tmp;
rightQ.add(tmp);
left++;
}
else {
int tmp = rightQ.poll();
sumRight -= tmp;
sumLeft += tmp;
leftQ.add(tmp);
right++;
}
}
// 반복문 벗어나면 limit
return -1;
}
}
두 큐가 주어질 때, 서로 값을 주고받으며 양쪽 큐의 값을 동일하게 만들 수 있는 최소 횟수를 반환하는 문제입니다.
한쪽 큐의 값이 더 크다면 반대쪽 큐로 값을 넘기는 방식으로 해결했습니다.
큐를 완성할 수 없는 예외를 판단하기가 너무 어려웠던 것 같습니다. 다른 블로그를 보니, 양쪽 큐가 각자 자신의 크기 * 2만큼 주고받으면 모든 경우의 수를 거친 것이라 합니다.