Level 2️⃣ - 두 큐 합 같게 만들기

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

프로그래머스

 

🚀접근 방법

직접 Map 자료형을 이용해 큐를 구현해서 해결하려했지만 시간초과가 계속 나왔다.

요소를 자료형에 저장하는 것이 아니라 포인터로 해결하는 방법이 더 효율적인 방법이었다.

 

오답 코드 (시간초과)

class Queue {
  constructor() {
    this.storage = new Map();
    this.front = 0;
    this.rear = 0;
  }
  size() {
    return this.storage.size;
  }
  push(value) {
    if (this.storage.size === 0) this.storage.set(0, value);
    else {
      this.rear += 1;
      this.storage.set(this.rear, value);
    }
  }
  pop() {
    let item = this.storage.get(this.front);
    if (this.storage.size === 1) {
      this.storage.clear();
      this.front = 0;
      this.rear = 0;
    } else {
      this.storage.delete(this.front);
      this.front += 1;
    }
    return item;
  }
}

function solution(queue1, queue2) {
  let ret = 0;
  let sum1 = BigInt(queue1.reduce((acc, cur) => acc + cur));
  let sum2 = BigInt(queue2.reduce((acc, cur) => acc + cur));
  let q1 = new Queue();
  let q2 = new Queue();
  queue1.forEach((elem, idx) => {
    q1.push(BigInt(elem));
    q2.push(BigInt(queue2[idx]));
  });
  while (q1.size() && q2.size()) {
    if (sum1 === sum2) return 0;
    else if (sum1 > sum2) {
      let elem = q1.pop();
      q2.push(elem);
      sum1 -= elem;
      sum2 += elem;
    } else if (sum1 < sum2) {
      let elem = q2.pop();
      q1.push(elem);
      sum1 += elem;
      sum2 -= elem;
    }
    ret++;
    if (sum1 === sum2) return ret;
  }
  return -1;
}

 

정답 코드

function solution(queue1, queue2) {
    let ret = 0;
    let pos1 = 0;
    let pos2 = 0;
    let totalLength = queue1.length + queue2.length;
    let sum1 = queue1.reduce((acc,cur)=>acc+cur);
    let sum2 = queue2.reduce((acc,cur)=>acc+cur);
    while(sum1 !== sum2){
        if(sum1 > sum2){
            sum2 += queue1[pos1];
            sum1 -= queue1[pos1];
            queue2.push(queue1[pos1]);
            pos1++;
        }
        else if(sum1 < sum2){
            sum1 += queue2[pos2];
            sum2 -= queue2[pos2];
            queue1.push(queue2[pos2]);
            pos2++;
        }
        ret++;
        if(pos1 > totalLength || pos2 > totalLength) return -1;
    }
    return ret;
}

 

if(pos1 > totalLength || pos2 > totalLength) return -1;

이 조건문이 이해가 되지 않았으나 잘 생각해보면 모든 요소를 한번씩 다른 큐에 주었고 다른 큐에서 모든 요소를 한번씩 받아왔음에도 정답을 찾을 수 없으면 정답을 찾을 수 없는 것이다.

왜냐하면 또 다시 모든 요소를 다른 큐에 주고 다른 큐에서 모든 요소를 받아오는 과정이 반복될 것이기 때문이다.

 

이 문제는 예외처리를 하는 부분이 까다로웠다. 처음에는 위의 조건식도 생각하지 못했다. 다른 코드를 살펴보니 자기 자신으로 돌아오는 경우의 수는 큐 길이 * 4라는 것을 이용해서 예외처리를 하는 코드도 있었다.

어떤 케이스에서 두 큐의 합이 같은 경우를 찾을 수 없는지를 조금 더 생각했어야했다.