프로그래머스 JS: 두 큐 합 같게 만들기

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

프로그래머스

 

🔒 문제

문제 설명

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

다음은 두 큐를 나타내는 예시입니다.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

1. queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
2. queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.

따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

---

제한사항

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
• 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

 

🔑 풀이

 

문제 접근 방법:

두 큐의 합을 저장해 놓고, 각 큐의 합들을 비교하여 값이 더 큰 큐에 원소를 작은 큐에 넣는 작업을 반복하여 두 큐의 합을 같게 만든다.

 

1) 접근

최소 횟수를 구하라고 해서 처음에는 어떤 알고리즘으로 풀어야 할지 고민했는데, 결과적으로 Queue라는 제한적인 자료구조이기 때문에 큰 배열의 값을 하니씩 빼서 작은 쪽에 대입하는 과정을 통해서 최소 작업을 할 수 있다.

 

2) 시간 줄여보기

두 배열의 주어진 길이가 같고, 합이 2로 나눠 떨어지는 두 큐의 합이 같아야 한다는 조건들이 주어지기 때문에 큐의 값을 저장해 놓고 재연산하지 않도록하면 시간을 아낄 수 있다.

처음에  케이스 2개가 시간초과가 떠서 시간을 줄여보고자 클래스 Queue를 만들어 사용했다.

배열 특성상 큐처럼 앞에 있는 원소를 dequeue하게 되면 문제없이 구현은 가능하지만 O(n)이 소요되기 때문에 while문 내에서 최대한 해당 연산들을 줄여보고자 enqueue, dequeue를 O(1)으로 수행할 수 있도록 해봤다.

 

3) 오류 수정

그러나 결론적으로 시간초과는 자료구조 문제가 아니었고, while문에서의 조건에 빈틈이 있었는지 무한하게 루프문이 돌아가서였다.

원래는 while문을 true로 두고 조건문에 부합하면 -1이나 answer를 return 하도록 했지만, 2개의 테스트케이스를 통과하지 못해서 while문의 조건을 고쳐주었다.

 

모든 연산이 최대로 queue * 3을 넘을 순 없으니 while문을 나갈 수 있는 조건을 추가적으로 달아주었다.

 

💻 코드

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor(value) {
    const newNode = new Node(value);
    this.first = newNode;
    this.last = newNode;
    this.length = 1;
  }
  enqueue(value) {
    const newNode = new Node(value);
    if (this.length === 0) {
      this.first = newNode;
    } else {
      this.last.next = newNode;
    }
    this.last = newNode;
    this.length++;
    return this;
  }
  dequeue() {
    if (this.length === 0) return false;
    let tmp = this.first;
    if (this.length === 1) {
      this.last = null;
    }
    this.first = this.first.next;
    tmp.next = null;
    this.length--;
    return tmp;
  }
}

function solution(queue1, queue2) {
  // 큐의 원소의 합과 전체 큐의 합
  let q1total = queue1.reduce((acc, cur) => acc + cur);
  let q2total = queue2.reduce((acc, cur) => acc + cur);
  const totalCount = q1total + q2total;
  const goalCount = parseInt(totalCount / 2);
  // 나눌 수 없다면 false
  if (totalCount % 2 !== 0) return -1;
  // 배열 큐로 만들기
  const qu1 = new Queue(queue1[0]);
  const qu2 = new Queue(queue2[0]);
  let count = 0;
  for (let i = 1; i < queue1.length; i++) {
    qu1.enqueue(queue1[i]);
    qu2.enqueue(queue2[i]);
  }
  let i = 0;
  while (i <= queue1.length * 3) {
    i++;
    if (
      q1total <= 0 ||
      q2total <= 0 ||
      q1total >= totalCount ||
      q2total >= totalCount
    )
      return -1;
    // 합이 더 큰 큐를 dequeue, 작은 큐에 enqueue
    if (q1total > goalCount) {
      const tmp = qu1.dequeue().value;
      qu2.enqueue(tmp);
      q1total -= tmp;
      q2total += tmp;
      count++;
    } else if (q1total < goalCount) {
      const tmp = qu2.dequeue().value;
      qu1.enqueue(tmp);
      q1total += tmp;
      q2total -= tmp;
      count++;
    } else {
      // 값이 같다면 return
      return count;
    }
  }
  // 찾는 값이 없다면 false
  return -1;
}