두개의 큐(queue1, queue2)합이 같아지기위한 이동횟수를 구하라
큐는 FIFO(first-in, first-out) 방식으로 처리
시간초과가 발생하여 해법 검색 후 수행 -> 투포인터 알고리즘 활용
조건
- 길이가 같은 두 개의 큐를 나타내는 정수배열 queue1, queue2가 매개변수로 주어짐
- 각 큐의 원소의 합을 같게 만들기 위해 필요한 작업의 최소횟수를 반환
- 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우 -1 반환
제한사항
- 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
- 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
- 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.
나의 풀이
- 시간초과가 발생하여 해법 검색 후 수행
- 각 큐별 합계를 구하고, 두 합계가 같아질 때 까지 반복적으로 큐간 원소이동을 진행했으나, 퍼포먼스이슈 발생
- js에서 .shift(), .push() 등을 실행할 때, 배열의 전체 원소를 순회하기 때문에 성능이슈가 발생한다고 함
- 해결법 검색 중 공통적으로 사용하는 로직 활용
- 2중 배열은 성능때문에 단일배열로 변환하여 처리하면서 두개의 배열에는 왜 이생각을 못했을까..
- 불필요할 수 있는 변수와 조건절을 많이 사용한 것 같기도
- 전달받은 두개의 큐(queue1, queue2) 배열을 하나의 큐(queue) 배열로 병합
- 몇가지 전처리 수행
- 큐1, 큐2 각각의 합을 구해 두개가 같은 경우: 리턴 0
- ∑queue2 (;sq2) 는 첫비교용만 사용되니 차라리 (∑queue)/2 (;h_sum) 와 ∑queue1 (;sq1) 의 값비교하는 것이 메모리 아끼는 방법일 듯
- ∑queue%2가 0인 경우: 리턴 -1
- 큐의 합이 홀 수 인 경우는 아무리 조립해도 나올 수 없기에 순회전에 미리 리턴
- 그런 경우가 없을 듯하나, 조건에도 반드시 짝수라는 얘기가 없기에 처리함
- 비교 대상인 합계구하기(h_sum; (∑queue)/2)
- 큐를 탐색하기위한 두개의 포인터를 선언
- 포인터1 : 시작점 -> 0
- 포인터2 : 큐2에서 가져올 데이터 시작점 -> queue1.length
- 큐 순회 이동수를 담는 cnt 선언 및 초기화; 0
- while 문을 이용하여 반복 순회
- for loop 보다 빠른속도, 비교대상 명확
- queue.length*3 한 이유
- queue2가 빈 배열인 경우, queue1의 원소를 하나씩 옮겨 값을 비교한다는 가정하에,
- 3을 곱한 이유 ?
- 단순하게 큐들의 길이가 최대 300,000이길래 3 곱함..
- 200,000일때는 2만 곱하면 되는지?.. 확인해봐야 알듯
- h_sum 보다 sq1 값이 작다면,
- sq1에 queue배열의 end 번째 값을 더하고, 포인트 오른쪽으로 이동
- h_sum 보다 sq1 값이 크다면,
- sq1에서 queue 배열의 start 번째 값을 빼고, 포인트 오른쪽으로 이동
- h_sum과 sq1이 같다면 누적한 이동횟수(cnt) 반환
function solution(queue1, queue2) {
const queue = [...queue1, ...queue2];
let sq1 = queue1.reduce(sum, 0);
let sq2 = queue2.reduce(sum, 0);
if (sq1 === sq2) return 0;
const t_sum = (sq1+sq2);
if (t_sum%2 != 0) return -1;
const h_sum = t_sum/2;
let start = 0;
let end = queue1.length;
let cnt = 0;
while(cnt <= queue.length*3) {
if (h_sum === sq1) {
return cnt;
} else if (h_sum > sq1){
sq1 += queue[end];
end++;
} else {
sq1 -= queue[start];
start++;
}
cnt++;
}
return -1;
}
const sum = (a, b) => a + b;
결과
