(Python/LV2) 두 큐 합 같게 만들기

문제 출처:https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

풀이:

 

from itertools import combinations
from collections import deque
def solution(queue1, queue2):
    mid = ( sum(queue1) + sum(queue2) ) // 2
    queue1,queue2 = deque(queue1), deque(queue2)
    valueable =set()
    for num in range(2,len(queue1) + len(queue2)):
        for i in list(combinations(( queue1+queue2) ,num)):
            valueable.add(sum(i))
    count = 0
    # -1 인 경우 구하기
    if mid not in valueable:
        return -1
    while sum(queue2) != sum(queue1):
        if sum(queue1) < sum(queue2):
            now = queue2.popleft()
            queue1.append(now)
            count += 1
        else:
            now = queue1.popleft()
            queue2.append(now)
            count += 1
    return count
    
6.7 / 100 ,,
-1 인 경우 구하는 combinations 빼면 63.3 점이 나온다

-1나오는 부분을 일단 생각해보자

 

from collections import deque
def solution(queue1, queue2):
    mid = ( sum(queue1) + sum(queue2) ) // 2
    queue1,queue2 = deque(queue1), deque(queue2)
    count = 0
    for i in range(len(queue1) * 4):
        if sum(queue1) < sum(queue2):
            now = queue2.popleft()
            queue1.append(now)
            count += 1
        elif sum(queue1) > sum(queue2):
            now = queue1.popleft()
            queue2.append(now)
            count += 1
        else: return count
    return -1
    
# 원상 복구 까지 돌아오려면 len 의 4를 곱해줘야함
# for 문으로 바꿔봄
시간초과  63.3 / 100

정답 답안

from itertools import combinations
from collections import deque
def solution(queue1, queue2):
    queue1,queue2 = deque(queue1), deque(queue2)
    count = 0

	
    sum_1 = sum(queue1)
    sum_2 = sum(queue2)
    for i in range(len(queue1) * 4):
        if sum_1 < sum_2:
            now = queue2.popleft()
            queue1.append(now)
            sum_1 += now
            sum_2 -= now
            count += 1
        elif sum_1 > sum_2:
            now = queue1.popleft()
            queue2.append(now)
            sum_1 -= now
            sum_2 += now
            count += 1
        else: return count
    return -1

sum 함수는 메모리를 엄청 잡아먹음

한 번만 해주고 나중에 안하려고 위로 빼준다