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

 

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

 

 

첫번째 풀이 (성공)

탈출조건, 시간초과를 어떻게 세울지 고민했다.

 

탈출조건

먼저 탈출조건은 두 큐의 합이 같거나 최대이동 횟수를 넘었을 때다

여기서 최대이동 횟수는 두 큐의 길이가 같으므로 queue1.length*2로 설정했다.

최대이동횟수 이상 이동하게 되면 -1을 리턴한다.

 

시간초과

shift의 시간복잡도는 O(n)으로 시간초과가 난다

따라서 shift를 사용하지 않고 shift 할 위치는 인덱스로 기억하고 push만 한다.

 

 

• 두 개의 큐의 합이 홀수이면 -1 리턴한다
• 각 큐의 shift할 인덱스 변수를 0으로 설정한다
• 각 큐의 합이 같거나 최대이동 횟수 전까지 두 큐의 합을 비교해 더하고 뺀다. queue1, queue2일 때
  • sum1 < sum2 이면 queue2에서 shift 한 값을 queue1와 sum1에 더해주고, sum2에서 뺀다
  • sum1 > sum2 이면 queue1에서 shift한 값을 queue2와 sum2에 더해주고, sum1에서 뺀다
• 이렇게 순회한뒤 sum1 = sum2이면 이동한 값을 리턴, 아니면 -1을 리턴한다

// 두 큐의 합이 같게 하기 위해 뺐다 넣다해야하는 최소횟수
// 안 되면 -1
// 둘의 합에서 빼주고 더해주고를 반복
function solution(queue1, queue2) {
    var answer = 0;
    let sum1 = getSum(queue1);
    let sum2 = getSum(queue2);
    let p1 = 0;
    let p2 = 0;
    const max = queue1.length * 3; // 300000
    
    if ((sum1 + sum2) % 2 === 1) return -1; // 둘의 합이 홀수면 불가능하므로 -1
    
    
    for (let i = 0; i < max; i++) {
        // 두 큐의 합이 같은경우
        if (sum1 === sum2) return answer;
        // 큐1의 합이 더 큰 경우 큐2로 이동
        if (sum1 > sum2) {
            const movingNum = queue1[p1];
            sum1 -= movingNum;
            sum2 += movingNum;
            queue2.push(movingNum)
            p1++;
        } 
        // 큐2의 합이 더 큰 경우 큐1로 이동
        else {
            const movingNum = queue2[p2];
            sum1 += movingNum;
            queue1.push(movingNum);
            sum2 -= movingNum;
            p2++;
        }
        answer++;
    }
    return -1;
}

function getSum(arr) {
    return arr.reduce((acc, curr) => acc + curr, 0);
}

 

 

최대이동 횟수를 여유롭게 3배까지 늘리니 풀렸다

다음과 같은 상황에서 A = [3, 3, 3, 3], B = [3, 3, 21, 3] 일 경우 두 큐의 합이 같게 되려면 9번 이동해야 한다

 

const maxCount = queue1.length*3;

 

 

배운점

• ≤ 300,000 인경우 *3을 떠올릴 수 있다.
• 특정한 경우가 통과 안 될 경우 범위를 넉넉하게 잡아본다
• 큐를 직접 구현할 수 있다

 

참고

https://school.programmers.co.kr/questions/41370

 

밑은 참고용 다른 방식 풀이이다. 

큐 사용

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

class Queue {
  constructor(list = []) {
    this.head = null;
    this.p = this.head;
    list.forEach((element) => this.enqueue(element));
    this.size = 0;
  }

  enqueue(element) {
    const newNode = new Node(element);
    if (!this.head) {
      this.head = newNode;
      this.p = newNode;
    } else {
      this.p.next = newNode;
      this.p = this.p.next;
    }
    this.size++;
  }

  dequeue() {
    const dequeueValue = this.head.value;
    this.head = this.head.next;
    this.size--;
    return dequeueValue;
  }
}

function solution(queue1, queue2) {
  let answer = -1;
  const n = queue1.length;
  let sum1 = queue1.reduce((acc, curr) => acc + curr, 0);
  let sum2 = queue2.reduce((acc, curr) => acc + curr, 0);
  const q1 = new Queue(queue1);
  const q2 = new Queue(queue2);

  while (answer < 3 * n) {
    answer++;
    if (sum1 === sum2) {
      return answer;
    }
    if (sum1 < sum2) {
      const dequeueValue = q2.dequeue();
      q1.enqueue(dequeueValue);
      sum1 += dequeueValue;
      sum2 -= dequeueValue;
    } else {
      const dequeueValue = q1.dequeue();
      q2.enqueue(dequeueValue);
      sum1 -= dequeueValue;
      sum2 += dequeueValue;
    }
  }
  return sum1 === sum2 ? answer : -1;
}

 

 

투포인터 사용

function solution(queue1, queue2) {
    const cq = queue1.concat(queue2);
    const n = cq.length;
    let answer = 0;
    let sum1 = queue1.reduce((acc, cur) => acc + cur, 0,);
    let sum2 = queue2.reduce((acc, cur) => acc + cur, 0,);
    let p1 = 0;
    let p2 = Math.floor(n / 2);

    while (p1 < n & p2 < n) {
        if (sum1 === sum2) {
            return answer
        }
        else if (sum1 > sum2) {
            const tmp = cq[p1++];
            sum1 -= tmp;
            sum2 += tmp;
        }
        else if (sum1 < sum2) {
            const tmp = cq[p2++];
            sum1 += tmp;
            sum2 -= tmp;
        }
        answer++;
    }

    return -1;
}