두 큐 합 같게 만들기 _ Lv.2*

이번 문제는 사실 문제를 보고 아무리 생각해봐도 어떻게 간단하게 풀 수 있지?라는... 두려움?? 때문에 30분 고민해보다가 다른 사람의 풀이를 참고했다. 근데 이거 그래도 한시간 고민 했으면 풀이 방법을 고안하지 않았을까 싶은 문제였다...

 

풀이는 두 큐의 합이 같아지는 elementSum을 구하여 이를 기준으로 합이 큰 큐는 원소를 빼주고, 합이 작은 큐에 그 원소를 넣어주는 방식으로 반복한다. 

 

그런데 이문제는 출제 원소에 따라 시간초과에 걸리는 부분이 있어서 while문의 횟수를 제한한다는 점, sum이 아니라 pop한 값을 더하고/빼는 방식으로 큐의 합을 구한다는 점을 통해 해결하였다.

 

그럼에도 불구하고! 아래의 풀이는 테케 2개에서 시간초과가 나왔다...ㅠ.ㅠ

from collections import deque
def solution(queue1, queue2):
    answer = 0  # 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수
    elementSum = int((sum(queue1) + sum(queue2)) // 2)
    queue1 = deque(queue1); queue2 = deque(queue2)
    qSum1 = sum(queue1); qSum2 = sum(queue2)

    while answer<(elementSum*3):
        if qSum1 == qSum2:
            return answer

        if qSum1 > elementSum:
            outE = queue1.popleft()
            queue2.append(outE)
            # qSum1 = sum(queue1); qSum2 = sum(queue2)
            qSum1 -= outE; qSum2 += outE
            answer += 1

        else:
            outE = queue2.popleft()
            queue1.append(outE)
            # qSum1 = sum(queue1); qSum2 = sum(queue2)
            qSum1 += outE; qSum2 -= outE
            answer += 1
    return -1

찾아보니 while에서 횟수 제한을 잘못했다. elementSum은 경우에따라 10 또는 더 많이 되기 때문에 시간초과에 걸리게 되는 것이다. 그래서 처음 queue1, 2의 길이의 3배로 변경하니 통과할 수 있었다.

from collections import deque
def solution(queue1, queue2):
    answer = 0  # 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수
    queue1 = deque(queue1); queue2 = deque(queue2); lenQueue = len(queue1)
    qSum1 = sum(queue1); qSum2 = sum(queue2)
    elementSum = int((qSum1 + qSum2) // 2)

    while answer<=(lenQueue*3):
        if qSum1 == qSum2:
            return answer

        if qSum1 > elementSum:
            outE = queue1.popleft()
            queue2.append(outE)
            qSum1 -= outE; qSum2 += outE
            answer += 1

        else:
            outE = queue2.popleft()
            queue1.append(outE)
            qSum1 += outE; qSum2 -= outE
            answer += 1
        print(queue1, queue2, answer)

    print(answer < len(queue1)*3)
    return -1