[프로그래머스] 두 큐 합 같게 만들기

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/118667

다른사람 코드를 생각하면서 써본 것

function solution(queue1, queue2) {
    let maxLength = queue1.length
    let queue1Sum = queue1.reduce((init,acc) => {return init += acc},0)
    let queue2Sum = queue2.reduce((init,acc) => {return init += acc},0)
    let result = 0
    let [i,j] = [0,0]
    while(queue1Sum != queue2Sum) {
        if(queue1Sum > queue2Sum) {
            queue2Sum += queue1[i]
            queue1Sum -= queue1[i]
            queue2.push(queue1[i])
            i+=1
        } else {
            queue1Sum += queue2[j]
            queue2Sum -= queue2[j]
            queue1.push(queue2[j])
            j+=1
        } 
        result += 1
        if(result >= maxLength*3) {
            result = -1
            break
        }
    }
    return result
}

풀긴 풀 수 있으나, 시간 복잡도에서 오류가 난다.
push는 시간복잡도가 '1' 소요되나, splice 같은 경우엔 모든 배열의 Re-indexing이 일어나기 때문에 사실상 정말 지양해야 하는 코드이다.
그래서 이번에 자바스크립트의 Queue 구현법을 공부해볼 겸, queue로 구현한 2번째 코드를 보여드리겠다.

function solution(queue1, queue2) {
    const queue_1 = new Queue(queue1)  
    const queue_2 = new Queue(queue2)
    const totalLength = queue1.length * 2
    let result = 0;
    while(true) {
        if(queue_1.sum < queue_2.sum) {
            queue_1.add(queue_2.popleft())
        } else if (queue_1.sum > queue_2.sum) {
            queue_2.add(queue_1.popleft())
        } else {
            return result
        }
        if(result > totalLength+1) {
            return -1
        }
        result += 1
    }
}
class Queue {
  constructor(queue) {
    this.storage = {...queue};
    this.sum = queue.reduce((init,acc) => {return init+=acc},0)
    this.front = 0;	
    this.rear = queue.length-1;	
  }
  add(value) {
      this.rear += 1;
      this.storage[this.rear] = value;
      this.sum += value
  }
  popleft() {
      let temp = this.storage[this.front]
      delete this.storage[this.front];
      this.front += 1;
      this.sum -= temp
      return temp
  }
}

코드는 길어보이지만, 시간복잡도 면에서는 아주 우수하다. 밑에 Queue 클래스로 되어있는 것이 큐를 자바스크립트로 구현한 것인데, 현재는 딕셔너리 형태로 구현을 해놓았다.

다른 사람의 코드를 보니, 현 상황에서는 더해주는 것만 고려를 하면 되었다...굳이 뺄 필요가 없기에 queue를 class 로 구현하지 않고도, 인덱스만 유지해준다면 충분히 풀 수 있었다.

총평 : 큐를 이용할 때 이 코드 조각을 쓸 수 있겠다는 생각이 들었다. 다음부터 큐와 관련된 문제가 나오면 shift, unshift, splice 같은 기능은 절대 쓰지 마리라.