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

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

프로그래머스

이 문제는 2022 테크 여름 인턴십 코딩 테스트에 나왔던 문제였습니다. 설레는 마음으로 풀었다가... 시간 초과의 벽에 부딪혀 결국 해설을 보았습니다.

해설

https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

2022 테크 여름인턴십 코딩테스트 해설

아이디어는 간단했습니다. queue1과 queue2의 원소들의 합을 각각 L, R이라고 할 때

• L > R이면, queue1의 원소를 queue2에 넘긴다.
• R > L이면, queue2의 원소를 queue1에 넘긴다.

두 queue의 합을 같게 만들기 위해서는 합이 큰 queue에서 작은 queue로 원소를 이동시켜야 하는 게 당연합니다. 사실 해설을 보기 전에 저도 이 방법으로 풀었습니다. 저 아이디어를 그대로 코드로 옮기면 아래와 같습니다.

from collections import deque

def solution(queue1, queue2):
    hap = sum(queue1) + sum(queue2)
    if hap % 2 != 0:
        return -1
    else:
        cnt = 0
        queue1, queue2 = deque(queue1), deque(queue2)
        while queue1 and queue2:
            if sum(queue1) > sum(queue2):
                queue2.append(queue1.popleft())
            elif sum(queue1) < sum(queue2):
                queue1.append(queue2.popleft())
            else:
                return cnt
            cnt += 1
        return -1

하지만 이 코드는 시간 초과가 발생합니다. 아마 두 queue의 합이 절대로 같아지지 않는 경우가 테스트 케이스로 주어졌을 때 시간 초과가 발생하지 않았나 추측하고 있습니다. 여기서부터 막혀서 결국 '질문하기' 탭에서 도움을 받았습니다.

다른 사람의 풀이

이 분의 풀이는 두 큐의 합을 비교하는 것이 아니라 하나의 큐의 합과 목표 합 사이의 비교를 이용해서 풀으셨습니다. 하나의 큐가 목표 합과 같아지면 자동적으로 나머지 큐도 목표 합과 같아집니다. 그래서 이 분의 풀이는 아래와 같습니다.

from collections import deque

def solution(queue1, queue2):
    hap = sum(queue1) + sum(queue2)
    if hap % 2 != 0:
        return -1
    else:
        cnt = 0
        mid_of_hap = hap // 2
        queue1, queue2 = deque(queue1), deque(queue2)
        q1_sum = sum(queue1)
        while queue1 and queue2:
            if q1_sum > mid_of_hap:
                tmp = queue1.popleft()
                q1_sum -= tmp
            elif q1_sum < mid_of_hap:
                tmp = queue2.popleft()
                q1_sum += tmp
                queue1.append(tmp)
            else:
                return cnt
            cnt += 1
        return -1

프로그래머스 채점 결과 최대 45.01ms, 37.9MB 소모했습니다.