문제 요약
길이가 같은 두 큐 queue1, queue2가 주어진다.
한 번의 작업은 다음과 같다.
한 큐에서 pop
pop한 원소를 다른 큐에 insert이 작업을 반복해서 두 큐의 원소 합을 같게 만들어야 한다.
가능한 최소 작업 횟수를 반환하고, 불가능하면 -1을 반환한다.
핵심 아이디어
두 큐의 전체 합을 total이라고 하자.
두 큐의 합이 같아지려면 각 큐의 합은 반드시 다음 값이 되어야 한다.
target = total / 2따라서 전체 합이 홀수라면 절대 두 큐의 합을 같게 만들 수 없다.
if total % 2 == 1:
return -1이후에는 queue1의 합을 target으로 만드는 과정을 생각하면 된다.
queue1의 합이 target보다 크면 queue1에서 원소를 빼서 queue2로 보낸다.
queue1의 합이 target보다 작으면 queue2에서 원소를 빼서 queue1으로 가져온다.
원형 배열로 생각하기
큐에서 pop한 원소는 다른 큐의 뒤에 들어간다.
이를 실제 큐로 구현할 수도 있지만, 두 큐를 이어 붙인 배열로 생각하면 포인터만으로 처리할 수 있다.
combined = queue1 + queue2초기 상태에서 queue1은 combined의 앞쪽 구간이다.
queue1에서 pop하는 것은 왼쪽 포인터를 오른쪽으로 이동하는 것과 같다.
queue2에서 pop해서 queue1에 넣는 것은 오른쪽 포인터를 오른쪽으로 이동하면서 값을 더하는 것과 같다.
풀이 과정
1. 전체 합과 목표 합 계산
total = sum(queue1) + sum(queue2)전체 합이 홀수라면 불가능하다.
그렇지 않다면 목표 합은 total // 2다.
2. 포인터 초기화
left = 0
right = len(queue1)초기 queue1 구간은 combined[0:right]이다.
current_sum은 현재 queue1의 합이다.
3. 현재 합에 따라 포인터 이동
현재 합이 목표보다 작으면 queue2에서 하나를 가져와야 한다.
current_sum += combined[right]
right += 1현재 합이 목표보다 크면 queue1에서 하나를 빼야 한다.
current_sum -= combined[left]
left += 1포인터는 원형처럼 움직일 수 있도록 인덱스에 나머지 연산을 사용한다.
4. 이동 횟수 제한
불가능한 경우 무한 반복에 빠지지 않도록 작업 횟수 제한을 둔다.
각 원소는 큐 사이를 여러 번 이동할 수 있지만, 최소 해를 찾는 과정에서는 포인터가 전체 배열 길이의 약 2배 이상 움직이면 더 이상 새로운 상태를 기대하기 어렵다.
일반적으로 다음 정도를 상한으로 둔다.
limit = len(queue1) * 3Python 코드
def solution(queue1, queue2):
total = sum(queue1) + sum(queue2)
if total % 2 == 1:
return -1
target = total // 2
n = len(queue1)
combined = queue1 + queue2
left = 0
right = n
current_sum = sum(queue1)
count = 0
limit = n * 3
while count <= limit:
if current_sum == target:
return count
if current_sum < target:
current_sum += combined[right % (2 * n)]
right += 1
else:
current_sum -= combined[left % (2 * n)]
left += 1
count += 1
return -1코드 설명
전체 합 확인
total = sum(queue1) + sum(queue2)두 큐의 합이 같아지려면 전체 합이 짝수여야 한다.
전체 합이 홀수라면 절반으로 나눌 수 없으므로 바로 -1을 반환한다.
목표 합
target = total // 2두 큐가 각각 가져야 하는 합이다.
이제 문제는 queue1의 합을 target으로 만드는 문제로 바꿀 수 있다.
이어 붙인 배열
combined = queue1 + queue2두 큐의 원소 이동은 결국 이 배열 위에서 구간을 이동하는 것처럼 볼 수 있다.
포인터 의미
left = 0
right = n현재 queue1에 해당하는 구간의 시작과 끝을 나타낸다.
초기에는 queue1이 combined[0:n]에 해당하므로 left = 0, right = n으로 시작한다.
합이 부족한 경우
if current_sum < target:
current_sum += combined[right % (2 * n)]
right += 1queue1의 합이 목표보다 작다면 queue2에서 원소를 하나 가져와야 한다.
이는 오른쪽 포인터를 확장하는 것과 같다.
합이 큰 경우
else:
current_sum -= combined[left % (2 * n)]
left += 1queue1의 합이 목표보다 크다면 queue1에서 원소를 하나 빼야 한다.
이는 왼쪽 포인터를 오른쪽으로 이동하는 것과 같다.
작업 횟수 제한
limit = n * 3불가능한 경우 포인터가 계속 돌 수 있으므로 제한을 둔다.
두 큐의 원소 수가 각각 n이므로 3n번 정도의 이동 안에 답이 나오지 않으면 만들 수 없다고 판단한다.
시간 복잡도
각 작업마다 포인터 하나만 이동한다.
최대 이동 횟수를 3n으로 제한하므로 시간 복잡도는 다음과 같다.
O(n)공간 복잡도
두 큐를 이어 붙인 배열 combined를 사용한다.
O(n)정리
이 문제는 큐를 직접 조작하는 대신 포인터로 해석하면 단순해진다.
핵심은 다음과 같다.
- 전체 합이 홀수면 불가능하다.
- 목표는
queue1의 합을 전체 합의 절반으로 만드는 것이다. queue1 + queue2를 원형 배열처럼 보고 포인터를 이동한다.- 현재 합이 작으면 오른쪽 포인터를 늘리고, 크면 왼쪽 포인터를 줄인다.
투 포인터 방식으로 O(n)에 해결할 수 있다.
