두 큐 합 같게 만들기

2022 KAKAO TECH INTERNSHIP

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

프로그래머스

실행 결과 : 실패

---

그리디인 것은 눈치챘지만 풀이방법에 전혀 손을 대지 못했다.

큐라는 개념이 나와 큐의 개념을 활용해 어떻게 문제를 풀지만 고민했고, 적절한 해답을 구하지 못했다.

 

문제부터 분석하자면 길이가 같은 두 개의 큐가 주어지고, pop과 insert를 진행하면서 두 큐의 합이 같게끔 만들어야한다.

단, 최소 작업 횟수를 구해야한다. 

 

우선 안되는 경우를 생각하면 모든 큐의 합을 구했을 때 2로 나누어떨어지지 않으면 두 큐의 합을 같게 만들어줄 수 없다.

이 경우에는 -1을 리턴하도록 구현해야한다.

q1 : [3, 2, 7, 2] // 14
q2 : [4, 6, 5, 1] // 16

 

두 큐의 합이 같아지려면 합이 큰 쪽에서 작은 쪽으로 숫자를 옮겨야한다.

따라서 q1의 합인 sum1과 q2의 합인 sum2를 구해서 비교한 후 큰 쪽에서 작은 쪽으로 숫자를 옮겨주고 작업횟수를 하나 늘려준다.

 

이렇게 합이 같아질 때까지 반복하면 되는데 기저조건이 필요하다.

원래 자기 상태로 돌아오면 이 경우에는 두 큐의 합을 같게 만들어줄 수 없는 경우가 된다.

3, 2, 7, 2 | 4, 6, 5, 1 ➡ 3, 2, 7, 2 | 4, 6, 5, 1

이렇게 원래 상태로 돌아오는데까지 "큐의 길이 * 4"만큼의 횟수가 걸리게 된다.

즉, 작업횟수가 "큐의 길이 * 4"만큼이 되면 원래 상태로 돌아왔다는 말이고 이 때 반복문을 빠져나와야한다.

| 4, 6, 5, 1, 3, 2, 7, 2 ➡ 작업횟수 : 4
4, 6, 5, 1 | 3, 2, 7, 2 ➡ 작업횟수 : 4
| 3, 2, 7, 2, 4, 6, 5, 1 ➡ 작업횟수 : 4
3, 2, 7, 2 | 4, 6, 5, 1 ➡ 작업횟수 : 4

총 작업횟수 : 16 ➡ 큐의 길이 4 * 4

 

코드

function solution(queue1, queue2) {
    let sum1 = queue1.reduce((acc, cur)=>acc+cur);
    let sum2 = queue2.reduce((acc, cur)=>acc+cur);
    let i = 0;
    let j = 0;
    const l = queue1.length;
    if((sum1 + sum2) % 2) return -1;
    let count = 0;
    while(count < 4 * l){
        if(sum1 === sum2) return count;
        else if(sum1 > sum2){
            let num = queue1[i++];
            sum1 -= num;
            queue2.push(num);
            sum2 += num;
        } 
        else {
            let num = queue2[j++];
            sum2 -= num;
            queue1.push(num);
            sum1 += num;
        }
        count ++;
    }
    return -1;
}

 

📝참고자료

https://www.youtube.com/watch?v=fS-qjGtNrb0