https://school.programmers.co.kr/learn/courses/30/lessons/118667
두 개의 큐의 합을 같게 만드는 평탄화 작업을 반복해야 하는 문제이다
큐의 모든 원소가 양수이므로 평탄화 작업을 반복할 수 있다.
먼저 두 큐의 합의 평균 sum = (sum1 + sum2) / 2
을 구함
sum1(또는 sum2)
이 sum
과 같으면 두 큐의 평탄화 횟수를 출력sum1
이 sum
보다 크면 queue1
에서 빼고 queue2
에 더함sum2
이 sum
보다 크면 queue2
에서 빼고 queue1
에 더함만약 sum
이 홀수라면 -1을 출력한다
만약 반복횟수 r1
, r2
가 queue의 크기의 두 배보다 커진 것은
평탄화작업을 반복하다가 사이클이 완료된 횟수이므로 -1을 출력한다
long sum1 = 0, sum2 = 0, sum;
for (long num1 : queue1) {
sum1 += num1;
longQueue1.add(num1);
}
for (long num2 : queue2) {
sum2 += num2;
longQueue2.add(num2);
}
입력받은 배열을 queue에 더하면서 합을 계산
int r1 = 0, r2 =0;
평탄화작업 반복횟수
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int solution(int[] queue1, int[] queue2) {
Queue<Long> longQueue1 = new LinkedList<>();
Queue<Long> longQueue2 = new LinkedList<>();
long sum1 = 0, sum2 = 0, sum;
for (long num1 : queue1) {
sum1 += num1;
longQueue1.add(num1);
}
for (long num2 : queue2) {
sum2 += num2;
longQueue2.add(num2);
}
sum = sum1 + sum2;
if(sum%2==1) return -1;
sum/=2;
int limit = queue1.length*2;
int r1 = 0, r2 =0;
while (r1 <= limit && r2 <= limit) {
if (sum1 == sum) return r1 + r2;
if (sum1 > sum) {
sum1 -= longQueue1.peek();
sum2 += longQueue1.peek();
longQueue2.add(longQueue1.poll());
r1++;
} else {
sum2 -= longQueue2.peek();
sum1 += longQueue2.peek();
longQueue1.add(longQueue2.poll());
r2++;
}
}
return -1;
}
}
limit을 어떻게 선언할지에 대한 내용이 어려웠다.