두 큐 합 같게 만들기

문제

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

접근 방법 && 풀이 변천사

카카오 블로그를 참고해서 알고보니 그리디 방식이라는 충격적인 소식을 접하고 .. 😳

그리디 방식으로 푸는데 이상하게 자꾸 시간초과가 걸렸다.

각각의 방식에서의 문제점을 간단히 다루고, 리팩토링 하고자 한다.

1. sum 내장 함수 활용해서 매 루프마다 합 비교 연산하기

from copy import deepcopy
from collections import deque


def is_equal(list1, list2):  # 같은 구성요소와 순서를 가진 리스트인지 확인
    if len(list1) != len(list2):
        return False
    for x1, x2 in zip(list1, list2):
        if x1 != x2:
            return False
    return True


def solution(queue1, queue2):
    if (sum(queue1) + sum(queue2)) % 2 == 1:
        return -1
    count = 0
    queue1, queue2 = deque(queue1), deque(queue2)
    init_queue1, init_queue2 = deepcopy(queue1), deepcopy(queue2)
    while sum(queue1) != sum(queue2):
        if is_equal(queue2, init_queue1) and is_equal(queue1, init_queue2):
            return -1
        if sum(queue1) > sum(queue2):
            queue2.append(queue1.popleft())
        else:
            queue1.append(queue2.popleft())
        count += 1

    return count

19 / 30 (11개 TC 모두 시간초과로 fail)

이번에 처음 안 사실인데, sum 함수는 시간복잡도가 O(n)이라고 한다.
sum이 파라메터로 받는 iterable의 요소 하나하나 접근하며 연산하는 방식이라 그런 것 같다.

그래서 sum을 없애고, 초기에 연산한 각 큐 별 sum 변수를 중심으로 연산하도록 바꿔보았다.

2. 각각의 sum 변수를 갱신하는 방식

from copy import deepcopy
from collections import deque


def is_equal(list1, list2):  # 같은 구성요소와 순서를 가진 리스트인지 확인
    if len(list1) != len(list2):
        return False
    for x1, x2 in zip(list1, list2):
        if x1 != x2:
            return False
    return True


def solution(queue1, queue2):
    sum1, sum2 = sum(queue1), sum(queue2)
    if (sum1 + sum2) % 2 == 1:
        return -1
    count = 0
    queue1, queue2 = deque(queue1), deque(queue2)
    init_queue1, init_queue2 = deepcopy(queue1), deepcopy(queue2)
    while sum1 != sum2:
        if is_equal(queue2, init_queue1) and is_equal(queue1, init_queue2):
            return -1
        if sum1 > sum2:
            popped = queue1.popleft()
            sum1 -= popped
            queue2.append(popped)
            sum2 += popped
        else:
            popped = queue2.popleft()
            sum2 -= popped
            queue1.append(popped)
            sum1 += popped
        count += 1

    return count

28 / 30 (2개 TC 역시 시간초과로 fail)

예 ..
새삼 이런 것도 해줘??! 라며 기쁘게 내장 함수를 낼름 써먹고 남발하는 걸 경계해야 한다는 걸 깨달았습니다 .. 🫠

그리고 또 신경 쓰이는 부분이 있다:

단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

이 조건 때문에 문제를 풀면서 제일 걸리는 건 언제 루프를 탈출할 것인가였는데, 역시 저 두 리스트를 비교하는 is_equal이 걸리긴한다.. (시간 복잡도 O(n))

3. 탈출 조건 재정립

몇번을 비교해야 초기 리스트와 같아질까?가 해당 문제에서의 탈출 조건의 요건이다.

처음 주어진 두 리스트의 길이가 같으므로, 이를 n이라고 치면 총 2 * n번의 연산(pop + insert)을 하면 각 리스트는 초기에 서로의 리스트와 같을 것이다. 다시 자기자신과 같아지려면, 또 한번 2 * n번의 연산을 해야한다. 즉, 4 * n이 될 것이다.

• 최종 코드

from collections import deque


def solution(queue1, queue2):
    sum1, sum2 = sum(queue1), sum(queue2)
    if (sum1 + sum2) % 2 == 1:
        return -1
    count = 0
    queue1, queue2 = deque(queue1), deque(queue2)
    init_qlen = len(queue1)
    while sum1 != sum2:
        if count >= init_qlen * 4:
            return -1
        if sum1 > sum2:
            popped = queue1.popleft()
            sum1 -= popped
            queue2.append(popped)
            sum2 += popped
        else:
            popped = queue2.popleft()
            sum2 -= popped
            queue1.append(popped)
            sum1 += popped
        count += 1

    return count

다른 블로그 풀이 참고해보니, 3 * n번의 연산으로 탈출할 수 있다고 하는데 여전히 이해는 잘 안된다🤔..