[프로그래머스] level2 : 두 큐 합 같게 만들기 - python

문제

풀이과정

이 문제 보고 처음 든 생각은... bfs스럽다라는 거였다.
그냥 모든 경우의 수를 다 돌아 보다가 두 큐의 합이 같아지면 그만두는 느낌이니까 말이다.
근데 bfs로 풀기에는 너무 큐에다가 넣어줄 요소들이 많아질 거 같아서 이게 맞나..? 싶긴 했지만
그래도 일단 풀어봤다.

시간 초과 코드

from collections import deque
import copy


def solution(queue1, queue2):
    answer = -2
    
   	len1 = len(queue1)

    sum_of_q1 = sum(queue1)
    sum_of_q2 = sum(queue2)

    queue1 = deque(queue1)
    queue2 = deque(queue2)

    target_sum = (sum_of_q1 + sum_of_q2) // 2

    dq = deque([(queue1, queue2, sum_of_q1, 0)])

    while True:
        q1, q2, sum1, count = dq.popleft()
        temp1 = copy.deepcopy(q1)
        temp2 = copy.deepcopy(q2)
		
        # 딱 반이 됐으면 그만
        if sum1 == target_sum:
            answer = count
            break
		
        # 적당히 이정도 돌아봤는데도 안되면 불가능하다고 판단
        if count > len1 * 3:
            return -1
		
        # 큐1 에서 요소를 빼서 큐2에 넣는 경우
        if temp1:
            elem1 = temp1.popleft()
            temp2.append(elem1)

            dq.append((temp1, temp2, sum1 - elem1, count + 1))
		
        # 큐2에서 요소를 빼서 큐1에 넣는 경우 
        if q2:
            elem2 = q2.popleft()
            q1.append(elem2)
            dq.append((q1, q2, sum1 + elem2, count + 1))

    return answer

결과는 초반에 몇개는 성공했는데, 뒤쪽에 시간초과가 우르르..

그래서 다른 사람의 코드를 봤다.
아이디어 자체는 비슷한데, 나는 모든 경우의 수를 다 따져봐야 한다고 생각해서 bfs를 쓴 건데
그게 아니라 합이 더 큰 큐에서 빼서 합이 더 작은 큐에다가 넣어주는 걸 반복하면 문제를 풀 수 있었다.
그래서 bfs를 쓰지 않아도 된다.

사실 나도 이 생각을 해봤었는데 무조건 합이 더 큰 큐에서 빼는 게 더 빠른가?를 생각해봤을 때
확실하지 않다 라고 생각해서 포기했었는데, 이러면 무조건 더 빨리 같은 수가 되나 보다;;

성공 코드

from collections import deque

def solution(queue1, queue2):
    answer = -2

    len_q1 = len(queue1)
    len_q2 = len(queue2)

    sum1 = sum(queue1)
    sum2 = sum(queue2)

    q1 = deque(queue1)
    q2 = deque(queue2)

    count = 0
    while True:
		
        # 적당히 돌려보다가 안되면 -1리턴
        if count > (len_q1 + len_q2) * 2: 
            return -1
		
        # 두 큐의 합이 같아지면 그만
        if sum1 == sum2:
            answer = count
            break
		
        # 큐2의 sum이 더 크면 큐2에서 뽑아서 q1에 넣음
        if q2 and sum1 < sum2:
            elem2 = q2.popleft()
            q1.append(elem2)

            sum1 += elem2
            sum2 -= elem2
		
        # 반대면 반대로
        elif q1 and sum1 >= sum2:
            elem1 = q1.popleft()
            q2.append(elem1)

            sum1 -= elem1
            sum2 += elem1
		
        count += 1

    return answer

여기서 찝찝한 건 -1을 리턴할 때 명확한 기준이 있는 게 아니라
적당히 돌려보다가 안되겠다 싶으면 -1을 return한다는 것..
맞긴 맞았지만 찝찝하다.

다른 사람의 풀이

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

    i, j = 0, len(queue1)-1
    curr = sum(queue1)
    count = 0

    while i < len(q) and j < len(q):        
        if curr == target:
            return count

        elif curr < target and j < len(q)-1:
            j += 1
            curr += q[j]

        else:
            curr -= q[i]
            i += 1

        count += 1

    return -1

투포인터로 풀 수도 있었구나