[KAKAO INTERNSHIP] 두 큐 합 같게 만들기 풀이 / JavaScript

프로그래머스

 

작성 코드 (1차 시도 / 타임 오버)

function getSum(q) {
  return q.reduce((acc, curr) => acc + curr, 0);
}
function solution(q1, q2) {
  let dest = parseInt((getSum(q1) + getSum(q2)) / 2);
  let tried = 0;
  while (true) {
    let a = getSum(q1);
    let b = getSum(q2);
    if (a === dest) {
      break;
    } else if (a < b) {
      q1.push(q2.shift());
      tried += 1;
    } else if (a > b) {
      q2.push(q1.shift());
      tried += 1;
    }
    if (tried === q1.length * 2) return -1;
  }
  return tried;
}

매번 각 큐의 합을 구하면서 더 적은 합을 가진 큐에 데이터를 넣어주는 방식으로 중간값을 찾아가는 방식입니다. 이 방식은 while문 안에서 getSum-O(n)과 shift-O(n)을 사용하기 때문에 n^2의 복잡도를 가집니다. 실패는 없지만 몇몇 케이스에서 타임오버가 발생합니다. 제한사항을 보면 최악의 경우 300000^2 수 만큼 데이터 연산이 발생하기 때문에 오버될 수 밖에 없었습니다.

 

작성 코드 (2차 시도 / 통과)

function solution(q1, q2) {
    let q1s = q1.reduce((acc, curr) => acc + curr, 0)
    let q2s = q2.reduce((acc, curr) => acc + curr, 0)
    let limit = q1.length * 3
    let dest = parseInt((q1s + q2s) / 2) // 목표값
    let d1 = 0
    let d2 = 0
    let tried = 0
    while (tried !== limit && q1s !== dest) {
        if (q1s < q2s) {
            q1.push(q2[d2])
            q1s += q2[d2]
            q2s -= q2[d2++]
        } else if (q1s > q2s) {
            q2.push(q1[d1])
            q2s += q1[d1]
            q1s -= q1[d1++]
        }
        tried += 1
    }
    return tried === limit ? -1 : tried
}

 

구현 로직

js에는 큐 라이브러리가 없기 때문에 head값만 옮겨주는 배열로 대신하여 사용했습니다. 

예를 들어 일반적인 큐에서 pop 동작은 배열의 start index(0)를 늘려주고(+1) insert 동작은 push로 대신합니다.

만약 변수 d1과 d2가 각각 q1, q2의 start index이고 q1에서 원소를 하나 빼서 q2에 넣어준다고 한다면 q2.push(q1[d1++]) 로 구현할 수 있습니다.

 

q1과 q2 중 더 적은 합을 가진 큐에 상대의 큐에서 값을 빼서 넣어주는 방식으로 계산하면서 목표값을 맞추면 그때의 시도 횟수를 리턴하고 만약 큐 길이의 3배까지 시도했는데도 목표값을 찾지 못한경우는 목표값을 만들기 불가능한 경우이므로 -1을 리턴합니다.

 

여기서 limit값을 2배보다 더 큰 배수로 지정한 이유는 큐에 큰 숫자가 한쪽에 몰려있는 경우 시도 횟수가 큐 길이의 2배 이상 발생할 수 있기 때문에 여유있게 지정합니다.