1. 입력과 출력
- 입력
- 길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2 ( 1 ≤ queue1 = queue2 ≤ 300,000 )
- 출력
- 각 큐의 원소 합이 같게 만들기 위해 필요한 작업의 최소 횟수 return : count || -1(원소 합이 같아지지 않을 경우)
2. 문제 풀이 로직
문제를 보자마자 생각난 방법은 투포인트였고, 실제로 가능한 것인지 일단 감을 잡기 위해 큐를 움직여보았다. push/pop을 실제로 구현할 지 아니면 push/pop이 된 것처럼 구현(투포인트, 슬라이딩 윈도우)을 할 것인지에 대해 정하기 위해서였다. 여러 테스트케이스들 중 일단 첫 번째 테스트케이스를 두고 진행해보았다.
사용한 테스트 케이스
queue1 : [3, 2, 7, 2] => 14점
queue2 : [4, 6, 5, 1] => 16점
모든 원소들을 합친 총합이 30점이므로 queue1과 queue2 각각 원소 합이 15씩 나뉘어져야 한다.
(1) 큐 두 개를 직접 push/pop하기? 혹은 (2) 투포인트? 어떻게 구현을 하면 좋을까?
해당 문제에서는 한 queue에서 원소를 pop하여 다른 queue로 push하는 것을 1회의 이동 횟수로 보았고, queue는 선입선출의 자료구조이기에 다음과 같이 움직일 것이다.
(1) 큐 두 개를 직접 push/pop하기
1회 이동 : queue1_pop, queue2_push
queue1 : 3 ---- [2, 7, 2] => [2, 7, 2] (합 : 11)
queue2 : [4, 6, 5, 1 + 3] => [4, 6, 5, 1, 3] (합: 19)
2회 이동: queue2_pop, queue1_push
queue1 : [2, 7, 2 + 4] => [2, 7, 2, 4] (합: 15)
queue2 : 4 ---- [6, 5, 1, 3] => [6, 5, 1, 3] (합: 15)
이렇게 2회의 이동만으로 각 queue의 원소 합이 15씩 골고루 나뉘어졌다. 하지만 Javascript 언어의 특성상 queue의 pop을 구현하는 것은 시간복잡도 상의 어려움이 있기에 (shift의 성능적인 문제, 맨 앞에 있는 요소를 제거한 뒤 다음 요소부터 한 칸씩 앞으로 당겨오는 구조이다.) queue의 pop을 구현할 때에는 실제 값을 빼고, 배열을 수정하기보다는 배열의 인덱스를 수정하는 방식을 많이 사용한다.
class Queue{
items=[]
front=0
constructor(arr){
this.items = arr
}
pop(){
return this.items[this.front++]
}
}
그렇다면, 이러한 pop() 메서드를 구현하지 않고 한 배열 내에서 포인트를 사용해서 queue를 구분해주는 구조를 사용하면 어떨까?
(2) 투 포인터 (원형 큐처럼 취급하기)
queue1과 queue2를 하나의 배열로 합쳐놓고, 두 개의 포인터를 사용해서 queue1이 어디부터 어디까지인지만 알 수 있다면 queue끼리의 구분은 물론이고, 각 queue의 누적합 또한 쉽게 구할 수 있을 것이다. 마치 하나로 이어진 원형큐처럼 보는 것이다.
queue : [3, 2, 7, 2, 4, 6, 5, 1]
↑ ↑
(0) ~ (3) = queue1
포인터는 start(0)와 end(queue1.length-1 = 3)로 설정한다.
그렇다면 위에서 queue끼리 push/pop을 진행했던 것처럼 포인터 두 개를 가지고 이동해보며 이해해보자.
1회 이동 : start(0 -> 1), end(3)
queue: [3, 2, 7, 2, 4, 6, 5, 1] => [2, 7, 2] (합 : 11)
↑ ↑
2회 이동 : start(1), end(3 -> 4)
queue: [3, 2, 7, 2, 4, 6, 5, 1] => [2, 7, 2, 4] (합: 15)
↑ ↑
위에서와 동일하게 포인터 두 개를 이용하여 최소 이동 횟수 2번이라는 결과물을 얻을 수 있다.
여기까지의 구조를 구현해보면, 원형 큐(queue1 + queue2)와 queue1.length, 원형 큐 원소들의 총합(30점), 구해야 할 합(15점) 그리고 투 포인터(start, end)를 구현할 수 있다.
function solution(queue1, queue2){
const queue = [...queue1, ...queue2] // 원형 큐
const n = queue1.length
const totalSum = queue.reduce((acc, cur) => acc + cur, 0) // 총합
const targetSum = totalSum / 2 // 각 큐의 동일한 누적합
// 총합이 홀수라면, 동일하게 나눌 수 없기에 바로 -1 return
if(totalSum % 2 !== 0) return -1
let start = 0
let end = n - 1
let count = 0 // return해야 할 이동 횟수
}
그렇다면 이제부터는 투 포인터를 언제, 어떻게 이동시킬 것인지에 대해 고민하고 구현하기만 하면 된다. 일단 어떤 queue든 동일한 합이면 되므로 queue1를 기준으로 합을 미리 구해놓고, 포인터를 움직여가면서 합을 더하거나 빼면 된다. 포인터를 움직이고 그 범위만큼 합을 새로이 구하는 것보다 미리 한 번 구해놓은 합을 연산하는 것이 훨씬 효율적이다.
let currentSum = queue1.reduce((acc, cur) => acc + cur, 0) // queue1의 합 미리 구하기
currentSum += queue2에서 pop한 원소
currentSum -= queue1에서 pop할 원소
그렇다면 어떻게 queue1 혹은 queue2에서 pop할 지 정할 수 있을까?
바로 현재 currentSum과 targetSum을 기준으로 잡으면 된다.
if(currentSum === targetSum) return count // 원소합이 동일하면, 결과값 return!
// 만약 동일해야 할 값보다 현재 값이 작으면, 원소를 더 추가해줘야함!
if(currentSum < targetSum) currentSum += queue2의 맨 앞 원소
// 반대로 동일해야 할 값보다 현재 값이 크면, 원소를 빼줘야 함!
else currentSum -= queue1의 맨 앞 원소
그럼 이제 queue2의 맨 앞 원소와 queue1의 맨 앞 원소를 알맞게 선택하기만 하면 된다. 헷갈리고 까먹기 전에 다시 한 번 원형 큐의 모습을 살펴보자. 여기서 queue2의 맨 앞 원소와 queue1의 맨 앞 원소를 가져오자면 어떻게 가져오면 될까?
초기 상태
queue : [3, 2, 7, 2, 4, 6, 5, 1]
↑ ↑
(0) ~ (3) = queue1
- queue1의 맨 앞 원소 : 당연하게도 queue[start]이다.
- queue2의 맨 앞 원소 : queue[end + 1]와도 같다.
다른 모양으로 한 번 더 확인해보자.
1번 이동 후
queue : [3, 2, 7, 2, 4, 6, 5, 1] => [2, 7, 2] (합: 11)
↑ ↑
(1) ~ (3)
- queue1의 맨 앞 원소 : 역시나 queue[start]이다.
- queue2의 맨 앞 원소 : queue[end + 1]와도 같다.
따라서 의사코드가 아니라 실제 구현한 코드는 다음과 같다. queue2의 원소를 추가하려면 먼저 end + 1를 해준 다음 queue2의 원소를 가져오면 되고, queue1의 원소를 제거하려면 start에 해당하는 원소를 합에서 빼준 다음 제거(start + 1) 해주면 된다. 또한 이는 push/pop 처럼 움직인 동작이므로 count++ 해준다.
if (currentSum === targetSum) return count
if (currentSum < targetSum) {
end += 1
currentSum += queue[end]
} else {
currentSum -= queue[start]
start += 1
}
count++
그럼 이제 이걸 얼마나 반복하면 될까?
처음에는 모든 원소의 길이(queue.length, 2n, n= queue1.length)만큼 다 이동해도 return되지 않는다면 동일한 합을 구하기 어려운 구조라고 생각했다. queue1의 길이만큼 queue2로 옮기고, 다시 queue2를 queue1로 모두 옮겨도 답이 나오지 않는다면 return -1를 해줘야 한다고 생각하였다.
while(count < queue.length + 1){
// 투포인터 동작 구현...{
// count ++
// }
}
return -1 // 구할 수 없음!
하지만 코드를 제출해보니 이보다 더 많은 최대 횟수가 필요하였고, queue.length * 2(4n) 만큼 돌아서 합쳐진 큐를 2바퀴 돌아도 답이 나오지 않는 것이 불가능한 풀이라는 것이 가장 정석의 기준이었다. 그러나 실제 문제 기준에서는 3n의 탐색만으로도 모든 경우를 커버할 수 있다는 chatGPT의 조언대로 queue1(n)의 3배까지 이동해보기로 하였다.
★ 문제점 발견! 투 포인터의 undefined 문제
만약 end(right 포인터)가 계속 증가하다가 배열의 범위를 벗어나는 순간, 배열을 참조할 수 없는 undefined 문제가 발생한다. 이는 두 가지 방법으로 해결할 수 있는데, 첫 번째는 전체 큐를 한 번 더 반복하여 붙이는 것이다. [...queue1, ...queue2]를 한 번 더 반복하기만 하면 되므로 구현이 쉬웠지만 그만큼 공간 메모리 사용이 증가한다는 특징이 있었다. 그래서 내가 택한 방법은 두 번째, mod 연산을 사용하는 것이다.
mod 연산을 통해 범위 내 이동으로 제한하는 방법인데 구현의 난이도가 많이 어렵지도 않고 메모리 또한 유지한 채로 사용할 수 있기에 바로 채택하였다. 투 포인터에 1를 더할 때 그 값이 총 배열을 넘어가지 않도록 다시 나누어주는 mod 연산으로 구현했다.
if (currentSum < targetSum) {
end = (end + 1) % queue.length
currentSum += queue[end]
} else {
currentSum -= queue[start]
start = (start + 1) % queue.length
}
따라서 이러한 과정들로 인해 나온 전체 코드는 이러하다.
3. 전체 코드
function solution(queue1, queue2) {
const queue = [...queue1, ...queue2]
const n = queue1.length
const totalSum = queue.reduce((acc, cur) => acc + cur, 0)
if (totalSum % 2 !== 0) return -1
const targetSum = totalSum / 2
let start = 0
let end = n - 1
let currentSum = queue1.reduce((acc, cur) => acc + cur, 0)
let count = 0
// 최대 이동 횟수는 원소 수의 3배까지 허용 (실제 문제 기준)
const maxMoves = n * 3
while (count <= maxMoves) {
if (currentSum === targetSum) return count
if (currentSum < targetSum) {
end = (end + 1) % queue.length
currentSum += queue[end]
} else {
currentSum -= queue[start]
start = (start + 1) % queue.length
}
count++
}
return -1
}