https://school.programmers.co.kr/learn/courses/30/lessons/118667
일단 첫 번째 생각은 틀렸었다 ㅋㅋ...
이래서 예시까지 모두 읽어보고 풀이를 시작해야하는 것 같다
나는 고정된 큐만을 생각하고 있었다. 그래서 " 맨 처음의 큐의 상태" 를 기반으로 누적합을 사용하는 것을 생각했었다.
그리고, insert, pop 이후 두 큐의 길이가 같아야 한다고도 생각하고 있었다... (아님)
그런데 이렇게 하면, 동적으로 변하는 큐를 고려하지 않게 되는 문제가 존재한다.
[1,2,1,2]
[1,10,1,2] 가 있는 경우 -> 총합 : 6 + 11 + 3 = 20 이다
->
[] 다(4) pop 해서 q2 에 insert
[1,10,1,2,1,2,1,2]
->
[1] q2 에서 하나 pop 해 옴 (5)
[10,1,2,1,2,1,2]
->
[1,10] q2 에서 하나 Pop 해옴 (6)
[1,2,1,1,2,1,2]
->
[10] q2 로 하나 insert 함 (7)
[1,2,1,1,2,1,2,1]
두 큐의 총합을 구해 이것을 A 라고 칭한다.
“최소 횟수" 라는 것이 걸렸었는데
어차피 A/2 보다 작으면 원소를 받아야지만 A/2 가 될 수 있다.
어차피 A/2 보다 크면 원소를 보내줘야 한다.
그리고 이 문제는 queue 라서 한 곳으로만 빼고, 한 곳으로만 받을 수 있어서, 그냥 A/2 보다 작으면 추가하고, 크면 빼는 식으로 생각해도 될 문제였다.
즉, Greedy 문제였다.
실제 Queue 에서 넣었다 뺐다 하기엔 뭔가 불안해서
위에서 생각했던 것 처럼 q1, q2 를 이어 붙여 사용하는 것으로 생각했다.
그리고 index 만을 사용하는 것이다. → 하나의 거대한 circular queue 처럼 생각하면 된다.
따라서 아래와 같이 하면 될 것 같다.
q1 에는 f1(front), r1(rear) 포인터를 갖고
q2 는 f2(front), r2(rear) 포인터를 갖는다
q1 을 기준으로만 한다.
하지만 이 경우, 불가능한 경우에는 “무한 반복" 을 하게 되기 때문에 “횟수 제한" 을 둬야 한다.
나는 각 큐 모두 한 번씩 다 이동된 횟수 → 즉, q1.len*2 면 충분하다고 생각했었다.
그런데 다음과 같은 경우가 존재한다. (🐳 반례의 중요성..!!)
따라서 q.len*3 까지만 반복하도록 한다.
이 “반복 횟수" 는 무한 루프를 돌아서 시간초과가 나는 것을 방지하는 용도 이기 때문에, 일정 수 이상의 값으로만 limit 을 주면돼서, 사실 명확하게 q.len*3 이 아닐 수도 있다. 이보다 작은 값의 limit 일 수도 있음.
class Solution {
public int solution(int[] queue1, int[] queue2) {
int answer = -2;
int len = queue1.length + queue2.length;
int[] total = concatenate(queue1,queue2,len);
long s1 = sum(queue1);
long s = sum(total);
if(s % 2 != 0) { // 총 합이 홀 수라면 두 큐의 합이 같아 질 수 없다
return -1;
}
answer = search(total, 0, queue1.length, queue1.length-1, len-1, s/2, s1);
return answer;
}
// 두 큐 를 길게 이어 붙인 결과를 리턴한다
private int[] concatenate(int[] q1, int[] q2, int len) {
int[] total = new int[len];
for(int i =0; i< q1.length; i++) {
total[i] = q1[i];
total[q1.length + i] = q2[i];
}
return total;
}
private int search(int[] arr, int front1, int front2, int rear1, int rear2, long target, long curSum) {
int f1 = front1; int f2 = front2;
int r1 = rear1; int r2 = rear2;
long s = curSum;
int len = arr.length; // 작업 횟수는 len 미만이어야 한다.
int cnt = 0;
boolean fail = true;
while(cnt <= (len + len / 2)) {
if(s == target) {
fail = false;
break;
}
else if ( s < target ) {
r1 = (r1 + 1) % len;
f2 = (f2 + 1) % len;
s += arr[r1];
cnt++;
} else {
s -= arr[f1];
f1 = (f1 + 1) % len;
r2 = (r2 + 1) % len;
cnt++;
}
}
if(fail) return -1;
return cnt;
}
private long sum(int[] arr) {
int len = arr.length;
long sum = 0;
for (long numb : arr) {
sum += numb;
}
return sum;
}
}