코드
def solution(queue1, queue2):
queue = queue1 + queue2
target = sum(queue) // 2
p1 = 0
p2 = len(queue1)
cnt = 0
cur = sum(queue1)
while p2 > p1 and p2 < len(queue):
if cur < target:
cur += queue[p2]
p2 += 1
elif cur > target:
cur -= queue[p1]
p1 += 1
else:
return cnt
cnt += 1
return -1
풀이
- 두 큐를 붙혀서 하나의 긴 리스트를 만들고, 각 큐의 시작점에 포인터 p1, p2를 놓으면 리스트[p1:p2]는 queue1과 동일하다.
- 따라서 p1을 증가시키는 것은 p1에서 pop한 후 p2에 insert하는 연산과 동일하고, p2를 증가시키는 것은 p2에서 pop한 후 p1에 insert하는 연산과 동일하다는 것을 알 수 있다.
- 그리고 두 연산은 서로 연관되지 않고 완전히 독립적이라는 것도 알 수 있다. 즉 1번 연산 후 2번 연산을 하는 것과 2번 연산 후 1번 연산을 하는 것은 동일하다(종료 조건이 아닌 경우).
- 종료 조건으로는 p1 >= p2, p2 >= len(리스트)로 정했다.
- p1 >= p2인 경우는 하나의 원소가 다른 모든 원소의 합보다 큰 경우이다.
- p2가 배열 길이보다 큰 경우 p2가 다시 리스트의 앞부분으로 옮겨진다고 해도 이미 고려된 경우라 배제한다.
- 따라서 저 조건에 만족하면서, queue1의 원소의 합이 절반 미만이면 p1을 증가시키고, 절반 초과면 p2를 증가시키는 과정을 반복하면 원하는 답을 찾을 수 있다.
리뷰
처음 문제를 만났을 때에는 어떤 식으로 풀어야될지 감을 잡지 못했다(BFS인줄 알았지만 큐의 길이가 300000인 것을 보고 아니라는 것을 깨달았다). 두 가지 연산을 하는 과정을 조금 따라해보다 보니 투포인터 문제라는 것을 눈치챌 수 있었다. 처음 문제를 보고 예시가 어떤 식으로 진행되는지 따라해보는 과정이 중요하다는 것을 느꼈다.
