Programmers / 두 큐 합 같게 만들기 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 두 큐 합 같게 만들기 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

from collections import deque

def solution(queue1, queue2):
    answer = 0

    repeat = len(queue1) * 2

    qu1 = deque(queue1)
    qu2 = deque(queue2)

    while repeat >= 0:
        if sum(qu1) == sum(qu2):
            return answer
        else:
            if sum(qu1) > sum(qu2):
                q1 = qu1.popleft()
                qu2.append(q1)
                answer += 1
            else:
                q2 = qu2.popleft()
                qu1.append(q2)
                answer += 1
        repeat -= 1

    return -1

 

매번마다 qu1, qu2의 sum을 구하려다가 보니깐 시간복잡도가 높아져서 틀렸다.

 

from collections import deque

def solution(queue1, queue2):
    answer = 0

    repeat = (len(queue1) + len(queue2)) * 2

    qu1 = deque(queue1)
    qu2 = deque(queue2)

    sum1 = sum(qu1)
    sum2 = sum(qu2)

    while sum1 != sum2:
        if sum1 > sum2:
            q1 = qu1.popleft()
            qu2.append(q1)
            sum1 -= q1
            sum2 += q1
            answer += 1
        else:
            q2 = qu2.popleft()
            qu1.append(q2)
            answer += 1
            sum2 -= q2
            sum1 += q2
        if repeat == 0:
            return -1
        repeat -= 1

    return answer

 

처음에 sum1, sum2를 구하고 나중에 차이가 생기면 qu1.popleft(), qu2.popleft()를 통해서 sum의 차를 구해서 비교하는 방식으로 풀어서 쉽게 풀었다.

---

※ 알아야 할 것

 

len(queue1) * 3의 경우를 생각해도 충분히 문제를 풀 수 있지만 큐가 들어갔다 나오는 최악의 경우까지 생각을 한다면

repeat = (len(queue1) + len(queue2)) * 2

 

이 경우의 수까지 계산하는 것이 좋다.