문제 풀이
- 큐 연산을 위해 디큐로 만든다 popleft를 사용하기 위해
- 두 큐의 합을 더한값을 구하고 그 값을 반으로 나누어 left,right로 나누어 가진다.
- 그 합을 이용하여 값이 큰쪽이 있으면 큰쪽의 가장 첫번째 값을 작은쪽에 준다
- 같아질때까지 비교한다.
여기에서 주의해야할 점은
- sum 함수를 얼마나 사용했는가?
- deque를 적절하게 사용했는가?
- 두 큐를 비교하는 최대값을 설정해주었는가
로 세가지로 볼 수있다.
해당 코드를 작성하면서 가장 처음으로 한 실수는 sum 함수를 남발한 것이다.
while 안에서 sum 함수를 남발하면 속도는 점점 느려지고 산으로 간다.
이러한 맥락에서 우리는 sum을 한번만 사용하여 큐에 추가 혹은 빠지는 값만큼 매번 더하고 빼준다
다음은 deque를 잘 사용하는 것이다. deque를 사용하는 것은 큐의 아이디어 때문에 사용하는 것도 있지만.
deque의 popleft()는 배열의 첫번째 데이터를 꺼내는 것으로 O(1)의 시간복잡도가 걸린다.
시간복잡도가 낮기 때문이기도 하다.
추가 정보는 이곳을 참고
마지막으로 루프하는 최대값을 설정하는 부분이다.
해당 부분은 정확하게 이해가 가지는 않았지만, 내가 지금까지 이해한 바로는
두 큐를 열심히 지지고 볶고 해서 연산을 했는데 다시 원래 큐 상태로 돌아가는 횟수를 limit으로 정한것이라고 생각한다.
그렇다면 왜 limit 이 두 큐의 길이를 합한것의 두배인가 ? 만약 큐의 길이가 4인 두 큐가 있을때 두 큐가 원래 자리로 돌아오려면 하나의 큐에 있는 모든 데이터가 다른 큐로 이동할때 이동횟수는 큐의 길이만큼일 것이다.
큐의 길이 만큼 이동하고 나면 원래의 큐에는 데이터가 없고 다른 큐에만 몰려있을 것이고 그 다른 큐에서도 똑같은 연산을 하면 4번이다. 그러면 두 큐가 서로 다른데이터만 가지고 있는것이지 똑같은 상황이다.
큐1 = [1,2,3,4]
큐2 = [5,6,7,8]
큐1 = [5,6,7,8]
큐2 = [1,2,3,4]
이런 상황이 되는거다 이게 다시 원상 복귀되는 상황을 가정하면 연산을 한번 더 해야하니까
(큐1의 길이 + 큐2의 길이) * 2 라는 값이 limit다.
라고 생각하기로 했다 (사실 이부분은 아직 헷갈린다 잘못되었다면 알려주시면 압도적 감사)
코드
from collections import deque
def solution(queue1, queue2):
lqueue = deque(queue1)
rqueue = deque(queue2)
left = sum(queue1)
right = sum(queue2)
limit = 2 * (len(queue1)+len(queue2))
# 두 큐가 원래 값으로 돌아오는 횟수
# limit까지 계산을 하면 두 큐 모두 원래 상태로 돌아오는 것이기 때문에
# limit 보다 작을때라고 기준치를 정해주어야 함
count = 0
if (left + right) % 2 == 1:
return -1
while count < limit :
if left == right:
return count
if left > right:
num = lqueue.popleft()
right += num
left -= num
#핵심 sum값에서 빼고,더하기를 통해 최대한 sum함수 호출을 최소화 함
rqueue.append(num)
else:
num = rqueue.popleft()
right -= num
left += num
lqueue.append(num)
count += 1
return -1