문제
코드
// 1개 시간초과, 2개 실패한 내 코드...
function solution(queue1, queue2) {
let ans = 0;
let qu1Sum = queue1.reduce((acc, cur) => acc + cur, 0);
let qu2Sum = queue2.reduce((acc, cur) => acc + cur, 0);
const qu1Origin = qu1Sum, qu2Origin = qu2Sum;
if(qu1Sum === qu2Sum) return ans;
let qu1Idx = 0, qu2Idx = 0
let qu1Leng = queue1.length, qu2Leng = queue2.length;
let qu1Stack = [], qu2Stack = [];
while(1) {
if(qu1Sum > qu2Sum) {
const target = queue1[qu1Idx]
qu2Stack.push(target);
qu1Sum -= target;
qu2Sum += target;
qu1Idx++;
if(qu1Idx === qu1Leng) {
queue1 = [...qu1Stack];
qu1Stack = [];
qu1Idx = 0;
qu1Leng = queue1.length;
}
}
else if(qu2Sum > qu1Sum) {
const target = queue2[qu2Idx]
qu1Stack.push(target);
qu2Sum -= target;
qu1Sum += target;
qu2Idx++;
if(qu2Idx === qu2Leng) {
queue2 = [...qu2Stack];
qu2Stack = [];
qu2Idx = 0;
qu2Leng = queue2.length;
}
}
else {
return ans;
}
// if(JSON.stringify(qu1Origin) === JSON.stringify(queue1) || JSON.stringify(qu2Origin) === JSON.stringify(queue2)) return -1;
if(qu1Origin === qu1Sum && qu2Origin === qu2Sum) return -1;
ans++;
}
}
// 이렇게 간단하게 풀다니...
function solution(queue1, queue2) {
let sum1 = queue1.reduce((acc, cur) => acc+cur, 0);
let sum2 = queue2.reduce((acc, cur) => acc+cur, 0);
let target = (sum1 + sum2) / 2;
let i1 = 0, i2 = queue1.length;
const max = queue1.length*3;
const newQueue = [...queue1, ...queue2];
for(let i=0; i<max; i++) {
if(sum1 === target) return i;
sum1 = sum1 > target ? sum1-newQueue[i1++] : sum1+newQueue[i2++];
}
return -1
}JS에는 큐가 없다...
- 큐가 없어 shift와 push를 이용해 풀어야해요! 근데 그러면 시간 초과가 나겠죠? 제가 시간 초과 났어요!!!
- 여기서는 두 큐의 길이가 같은 특징을 이용해 두 큐를 붙여 계산하였어요!
탈출 조건
- 탈출 조건이 사실 세뇌시켜서 이해한 거지 확실히 이해는 가지 않아요...
len * 4
- 두 큐를 서로 바꾼다는 조건일 때 길이의 두 배가 소요되니까 len*2
- 다시 원상복귀 할 때 *2니까 4라고 해요
len * 3
- newQueue에서 queue1Idx가 0에서 최대 len2까지 갈 수 있고, queue2Idx는 len~len2까지 갈 수 있어요
- 두 개를 합치면 len*3
JSON.stringify를 이용해 배열 비교
- 배열은 참조형 변수라 각각 주소 값이 달라요
[1, 2, 3] === [1, 2, 3] // false- 이거를 비교하는 가장 빠른 방법은 JSON.stringify를 이용하는 거에요!
JSON.stringify[1, 2, 3] === JSON.stringify[1, 2, 3] // true참고 사이트
쿼카에요