[프로그래머스 / 파이썬] 두 큐 합 같게 만들기

프로그래머스

정답 코드

def solution(queue1, queue2):
    queue3 = queue1 + queue2
    target = sum(queue3) // 2

    if sum(queue3) % 2 != 0:
        return -1

    queue = queue1 + queue2 + queue1
    max_count = len(queue)

    answer, left, right, sum_value = 0, 0, len(queue1), sum(queue1)

    while answer <= max_count:
        if sum_value == target:
            return answer
        elif sum_value < target:
            sum_value += queue[right]
            right += 1
            answer += 1
        elif sum_value > target:
            sum_value -= queue[left]
            left += 1
            answer += 1

    return -1

문제 풀이

두 큐 합 같게 만들기 문제는 주어진 두 개의 큐(queue1, queue2)를 합쳐서 한 개의 큐로 만들고, 큐의 원소들을 재배치하여 두 큐의 합이 같아지도록 하는 것입니다. 만약 두 큐의 합이 같아질 수 없다면 -1을 반환해야 합니다.

이 문제를 해결하기 위해 투 포인터 알고리즘을 사용하였습니다. 이제 코드의 동작 방식을 자세히 설명하겠습니다:

1. `queue1`과 `queue2`를 합쳐서 `queue3`을 생성합니다.

2. `target`을 계산하여 두 큐의 합을 2로 나눈 몫으로 설정합니다.
    이는 두 큐의 합이 같아지기 위해 가져야 하는 각 원소들의 합입니다.

3. 두 큐의 합이 홀수인 경우, 두 큐의 합이 같아질 수 없으므로 -1을 반환합니다.

4. `queue1`을 두 번 반복한 `queue` 리스트를 만듭니다. (이유는 아래 설명하겠습니다.)

5. `answer`, `left`, `right`, `sum_value` 변수를 초기화합니다.
   - `answer`: 두 큐의 합이 같아지기 위해 이동해야 하는 횟수를 저장합니다.
   - `left`: 큐의 왼쪽 포인터로 사용될 변수를 초기화합니다.
   - `right`: 큐의 오른쪽 포인터로 사용될 변수를 `queue1`의 길이로 초기화합니다.
   - `sum_value`: 현재 포인터들이 가리키는 구간의 원소들의 합을 저장합니다.

6. 반복문을 실행하며 두 큐의 합이 같아지도록 조정합니다.
   - `sum_value`이 `target`과 같다면 `answer`를 반환하고 종료합니다.
   - `sum_value`이 `target`보다 작다면, 오른쪽 포인터를 한 칸 이동시켜 구간 합을 증가시킵니다. 동시에 `answer`도 증가시킵니다.
   - `sum_value`이 `target`보다 크다면, 왼쪽 포인터를 한 칸 이동시켜 구간 합을 감소시킵니다. 동시에 `answer`도 증가시킵니다.
   - 이후 다시 반복하여 `sum_value`이 `target`과 일치할 때까지 오른쪽 또는 왼쪽 포인터를 이동시키면서 합을 조정합니다.

7. 반복문이 종료되면 여전히 두 큐의 합이 같아지지 않은 경우, -1을 반환합니다.

이 코드의 핵심 아이디어는 `queue1`을 두 번 반복하여 `queue`에 저장한 뒤, 투 포인터 알고리즘을 적용하는 것입니다. `queue` 리스트를 두 번 반복한 이유는, 투 포인터 알고리즘을 사용하기 위해서는 반복되는 구간을 고려해야 하기 때문입니다. 이렇게 함으로써 `left`와 `right` 포인터가 `queue1`의 끝에서 `queue1`의 시작으로 순환하면서 모든 경우의 수를 고려할 수 있습니다.

투 포인터 알고리즘은 선형 시간복잡도를 가지므로, 이 코드의 시간 복잡도는 O(n)이 됩니다. 여기서 n은 `queue1`과 `queue2`의 크기의 합입니다. 따라서 상대적으로 효율적으로 작동할 수 있습니다.