휴지통/알고리즘 & 자료구조
두 큐 합 같게 만들기
by 신재권
2023. 2. 26.
package programmers;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.Collectors;
public class 두_큐_합_같게_만들기 {
public static int solution(int[] queue1, int[] queue2) {
long queue1Sum = sumQueue(queue1);
long queue2Sum = sumQueue(queue2);
long sum = (queue1Sum + queue2Sum);
if (sum % 2 == 1) {
return -1;
}
sum /= 2;
Queue<Integer> q1 = Arrays.stream(queue1).boxed().collect(Collectors.toCollection(LinkedList::new));
Queue<Integer> q2 = Arrays.stream(queue2).boxed().collect(Collectors.toCollection(LinkedList::new));
int p1 = 0;
int p2 = 0;
int limit = queue1.length * 2;
while (p1 <= limit && p2 <= limit) {
if (queue1Sum == sum) {
return p1 + p2;
}
if (queue1Sum > sum) {
queue1Sum -= q1.peek();
queue2Sum += q1.peek();
q2.add(q1.poll());
p1++;
} else {
queue2Sum -= q2.peek();
queue1Sum += q2.peek();
q1.add(q2.poll());
p2++;
}
}
return -1;
}
private static long sumQueue(int[] queue) {
return Arrays.stream(queue).sum();
}
public static void main(String[] args) {
System.out.println(solution(new int[] {3, 2, 7, 2}, new int[] {4, 6, 5, 1}));
System.out.println(solution(new int[] {1, 2, 1, 2}, new int[] {1, 10, 1, 2}));
System.out.println(solution(new int[] {1, 1}, new int[] {1, 5}));
}
}