📗 두 큐 합 같게 만들기

프로그래머스

첫 번째 접근: deque()

from collections import deque

def solution(queue1, queue2):
    queue1, queue2 = deque(queue1), deque(queue2)
    sum1, sum2 = sum(queue1), sum(queue2)
    target = (sum1 + sum2) // 2
    
    if (sum1 + sum2) % 2 != 0:
        return -1
    
    cnt = 0
    max_cnt = len(queue1) * 3
    
    while sum1 != target:
        if cnt > max_cnt:
            return -1
        if sum1 > sum2:
            e = queue1.popleft()
            sum1, sum2 = sum1 - e, sum2 + e
            queue2.append(e)
            cnt += 1
        elif sum1 < sum2:
            e = queue2.popleft()
            sum1, sum2 = sum1 + e, sum2 - e
            queue1.append(e)
            cnt += 1
            
    return cnt

• 2022 KAKAO TECH INTERNSHIP 코딩테스트 문제 중 하나인 '두 큐 합 같게 만들기' 입니다.

왜 이렇게 풀었을까?

• 문제와 문제 설명에도 나와있듯 '큐'를 사용하여 푸는 문제로 판단하고 바로 collections 모듈을 꺼내서 코드를 작성해보았습니다.
• 우선 두 큐의 총합이 홀수인 경우에는 두 큐의 합을 같게 만들 수 없기 때문에 처리를 해주었고,
• max_cnt의 설정은 이론적으로 두 큐의 모든 원소를 한 번씩 옮기는 데 필요한 최대 횟수가 2n이며, 조금 더 여유를 주기 위해서 3n으로 설정해두었습니다. 이렇게 해서 무한 루프도 피하고, 시간도 조금 줄일 수 있게 되었습니다!
• 처음에는 매 반복마다 sum1, sum2에 sum(queue1), sum(queue2)를 할당하였는데 매 반복마다 이를 계산하다보니 시간적으로 효율성이 떨어지는 것을 발견하였습니다. 때문에 간단한 사칙 연산으로 이를 변경하였습니다.
• 하지만 popleft()나 append()의 경우에도 매 반복마다 이루어져서, 이를 인덱스로 접근해보면 어떨까 생각해보다가 생각해 낸 기법이 '슬라이딩 윈도우' 기법이었습니다.

---

두 번째 접근: 슬라이딩 윈도우

def solution(queue1, queue2):
    q = queue1 + queue2
    sum1 = sum(queue1)
    total = sum1 + sum(queue2)
    target = total // 2
    
    if total % 2 != 0:
        return -1
    
    n = len(queue1)
    start, end = 0, n
    
    for cnt in range(n * 3):
        if sum1 == target:
            return cnt
        elif sum1 > target:
            sum1 -= q[start]
            start += 1
        else:
            if end == len(q):
                return -1
            sum1 += q[end]
            end += 1
    
    return -1

왜 이렇게 풀었을까?

• 두 큐(queue1, queue2)를 하나로 합친 상태에서 인덱스로만 접근을 하게 되니 deque에서의 연산을 사용하지 않아도 되어 실행 시간이 크게 줄었습니다.
• start, end를 사용하여 윈도우를 이동시키는 방법으로 실제 큐에서 원소를 이동시키는 것보다 훨씬 효율적인 방법이 되었습니다.
• 또한 sum을 구하는 것도 큐 하나의 합만 구하면 된다고 판단하여 다른 큐의 합은 구할 필요가 없게 되었습니다.