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

1. 문제

두 큐 합 같게 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/118667

이진 탐색을 생각하지 못해서 시간초과로 풀지 못했다. 하지만 점점 다시 감을 찾아가는 거 같아 흥미가 진진하다. 그럼 고고

2. 나의 틀린 풀이

function solution(queue1, queue2) {
    var answer = -2;
    const prev1 = queue1
    const prev2 = queue2
    
    let sum1 = queue1.reduce((a,b) => a+b,0)
    let sum2 = queue2.reduce((a,b) => a+b,0)
    
    let count = 0
    
    while(sum1!==sum2){
        if(sum1 > sum2){
            queue2.push(queue1[0])
            sum1 -= queue1[0]
            sum2 += queue1[0]
            queue1 = queue1.slice(1)
        }
        else{
            queue1.push(queue2[0])
            sum2 -= queue2[0]
            sum1 += queue2[0]
            queue2 = queue2.slice(1)
        }
        if((prev1.filter((e,i) => queue1[i] !== e ).length === 0 && prev2.filter((e,i) => queue2[i] === e).length !== 0)){
            count = -1
            break
        }
        count ++
    }
    answer = count
    
    return answer;
}

딱 봐도 구질구질하다.

가장 큰 패인은 답이 나오지 않을 때의 조건을 생각하지 못한 것이다.

두번째 패인은 위의 패인과 연결이 된다.
배열 간의 비교를 잘못 알고 있었다.

[1,2] === [1,2] => false

그래서 배열 간의 비교는 filter를 통해 가능하다.

세번째 패인은 코드가 계속 길어지면서 점점 미궁에 빠지게 되었다는 것이다.

결국 비교를 했는데 계속 false가 뜨고 무한루프가 나와서, 시간초과를 계속 먹게 되었다.

결국 다른 분들의 코드를 참고했다...

2. 멋진 분의 코드

풀이 1

function solution(queue1, queue2) {
    let answer = 0;
    const list = [...queue1, ...queue2];
    let lt = 0;
    let rt = queue1.length - 1;
    const totalSum = list.reduce((acc, val) => acc + val, 0);
    let subSum = queue1.reduce((acc, val) => acc + val, 0);

    while (lt <= rt) {
        if (totalSum - subSum === subSum) return answer;
        if (subSum < totalSum - subSum) {
            rt++;
            subSum += list[rt];
            answer++
        }
        else {
            subSum -= list[lt];
            lt++;
            answer++

        }
    }
    return -1;
}

[...a, ...b] 하면 코드가 합쳐지는 거 유용하게 쓸 거 같다.

풀이 2

function solution(queue1, queue2) {
  const n = queue1.length;
  const queue = [...queue1, ...queue2];

  const sum1 = queue1.reduce((acc, cur) => acc + cur, 0);
  const sum2 = queue2.reduce((acc, cur) => acc + cur, 0);
  const half = (sum1 + sum2) / 2;

  let sum = sum1;
  let count = 0;

  let start = 0;
  let end = n - 1;
  while (count < 4 * n) {
    if (sum === half) {
      return count;
    }
    count += 1;

    if (sum < half) {
      end += 1;
      sum += queue[end];
      continue;
    }
    if (sum > half) {
      sum -= queue[start];
      start += 1;
      continue;
    }
  }
  return -1;
}

위의 코드와 비슷하나 더 이진탐색트리의 형식에 맞는 거 같아 가져왔다.

결국 풀이 1의 코드를 참고하여 문제를 풀었다. 이진탐색 트리 관련 문제를 더 풀어봐야지!

3. Binary Search Algorithm