[프로그래머스] 두 큐 합 같게 만들기 / Python, JavaScript / Level 2

🚩문제 주소

📄풀이

Python
주어진 queue를 deque로 바꿔줍니다.

반복을 최대한 줄여야 하기 때문에, queue의 합을 미리 설정해주고, while 대신 for를 활용하여 첫 번째 큐의 3배 길이까지 반복합니다.

• 첫 번째 큐의 합과 두 번째 큐의 합이 같을 경우, 횟수를 리턴합니다.
• 첫 번째 큐의 합이 두 큐의 합의 절반보다 클 경우, 첫 번째 큐.popleft()를 해서 두 번째 큐에 push, 첫 번째 큐의 합에서 빼기, 두 번째 큐의 합에 더하기, 횟수 +1을 합니다.
• 첫 번째 큐의 합이 두 큐의 합의 절반보다 작을 경우, 두 번째 큐.popleft()를 해서 첫 번째 큐에 push, 두 번째 큐의 합에서 빼기, 첫 번째 큐의 합에 더하기, 횟수 +1을 합니다.

반복을 다 했는데도 두 큐의 합이 같지 않다면 -1을 리턴합니다.

JS
자바스크립트에서는 shift연산이 굉장히 오래걸려서 시간 초과가 나기 때문에 투 포인터 알고리즘을 사용해서 풀어야 했습니다.

두 큐를 합치고, 포인터 두 개를 각각 0과 첫 번째 큐.length로 설정해줍니다.
반복은 첫 번째 큐 길이의 3배 만큼 합니다.

• 두 큐의 합이 같다면 현재 인덱스를 리턴합니다.
• 첫 번째 큐의 합이 두 큐의 합의 절반보다 클 경우, 첫 번째 큐의 합에서 합친 큐의 첫 번째 포인터 위치의 수를 빼주고, 포인터를 증가시킵니다.
• 첫 번째 큐의 합이 두 큐의 합의 절반보다 작을 경우, 첫 번째 큐의 합에서 합친 큐의 두 번째 포인터 위치의 수를 더해주고, 포인터를 증가시킵니다.

반복을 다 했는데도 두 큐의 합이 같지 않다면 -1을 리턴합니다.

👨‍💻코드

# Python
from collections import deque

def solution(queue1, queue2):
    q1 = deque(queue1)
    q2 = deque(queue2)
    answer = 0
    goal = (sum(q1)+sum(q2)) / 2
    q1_sum, q2_sum = sum(q1), sum(q2)
    
    for _ in range(len(queue1)*3):
        if q1_sum == q2_sum:
            return answer
        
        elif q1_sum > goal:
            temp1 = q1.popleft()
            q2.append(temp1)
            q1_sum -= temp1
            q2_sum += temp1
            answer += 1
        
        else:
            temp2 = q2.popleft()
            q1.append(temp2)
            q1_sum += temp2
            q2_sum -= temp2
            answer += 1
    
    return -1

// JS
function solution(q1, q2) {
    let sum1 = q1.reduce((acc, cur)=>acc+cur);
    let sum2 = q2.reduce((acc, cur)=>acc+cur);
    const goal = (sum1 + sum2) / 2;
    let p1 = 0;
    let p2 = q1.length;
    const q = [...q1, ...q2];
    
    for (let i=0; i<q1.length*3; i++) {
        if (sum1 === goal) return i;
        
        if (sum1 > goal) sum1 -= q[p1++];
        
        else sum1 += q[p2++];
    }
    
    return -1;
}