참고
문제해설
문제 로직고민
NOTE
•
두개의 큐의 모든 합을 구하고 그 절반의 값을 만들 수 있는지 확인한다.
◦
2개의 큐에서 절반의 값보다 큰쪽을 추출한다.
◦
해당 과정을 반복하며 2개의 큐가 모두 절반의 값이 충족하는 최소단계를 찾는다.
•
2개의 큐가 절반값을 맞출수 없는 경우는 합이 홀수이거나, 절반값을 만들 수 없는 경우다.
◦
2개의 큐를 하나의 일자로 연속해서 보면 끝점을 어디에 두냐에 따라 2개의 공통된 합이 나타나는 구간이 있어야한다.
◦
즉 2개의 큐를 합친만큼 반복했는데 실패한다면 불가능하다는 것!
작성코드
NOTE
class Solution {
static int func(Deque<Integer> q1, Deque<Integer> q2, long sum1, long sum2){
int cnt =0;
long targ = (sum1+sum2)/2;
int len = q1.size()*3;
int idx= 0;
while(idx<len){
idx++;
if(sum1>sum2){
int val = q1.poll();
q2.add(val);
sum1-=val;
sum2+=val;
cnt++;
}else if(sum1<sum2){
int val = q2.poll();
q1.add(val);
sum1+=val;
sum2-=val;
cnt++;
}
else return cnt;
}
return -1;
}
public int solution(int[] queue1, int[] queue2) {
int answer = -2;
long sum1 =0;
long sum2 =0;
Deque<Integer> q1 = new ArrayDeque<>();
Deque<Integer> q2 = new ArrayDeque<>();
for(int i =0;i<queue1.length;i++){
sum1+=queue1[i];
sum2+=queue2[i];
q1.add(queue1[i]);
q2.add(queue2[i]);
}
if(sum1==sum2)return 0;
answer=func(q1,q2,sum1,sum2);
return answer;
}
}
Java
복사
참고코드