[프로그래머스] 두 큐 합 같게 만들기 [Level 2] (python 파이썬)

https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

from collections import deque

def solution(queue1, queue2):
    q1 = sum(queue1) 
    q2 = sum(queue2)
    s = q1 + q2
    target = s/2

    if q1  == target:
        return 0
    queue1 = deque(queue1)
    queue2 = deque(queue2)

    n = 0
    a = 0
    while 1 :
        a += 1
        if a>300000:
            return -1
        if q1 > q2:
            q1_0 = queue1.popleft()
            queue2.append(q1_0)

            if q1_0 > target:
                return -1

            q1 = q1 - q1_0
            q2 = q2 + q1_0
            n += 1
            if q2  == target:
                return n
        else:
            q2_0 = queue2.popleft()
            if q2_0 > target:
                return -1
            queue1.append(q2_0)
            q1 = q1 + q2_0
            q2 = q2 - q2_0
            n +=1
            if q1 == target:
                return n

 

 

 

 

문제가 두 큐 합 만들기인 만큼 큐를 사용하여 풀었다. 

 

 

 

1. q1의 합과 q2의 합을 구한다.  ( 그래야 목표값을 알 수 있기 때문)

(이때 q1이나 q2 중 아무거나 목표값에 다다르면 정답!)

 

 

2. 목표값을 구한다.

 

3. 만약 목표값이 이미 도달해 있다면 0 리턴 ( 처음부터 정답이 입력될 수 있기 때문)

 

4. while문 안에서 동작

 

4-1. q1 과 q2 중 더 큰 값에서 popleft 해서 작은 값에 append 한다.  

4-2. append 했을 때의 값이 target과 같으면 n 리턴

4-3. 4-1과 4-2 연산을 300000번 이상 했을 땐, 이미 했던 연산을 반복하고 있다는 뜻으로 답이 없다. 따라서 -1 리턴

 

 

 

 

 

문제의 목표는 각각의 큐의 합이 같게 되어야 한다.

그러려면 각각의 큐의 합을 알아야 하며, 모든 큐의 합을 알아야 한다.

 

두 큐의 합이 다르다면 , 둘 중 하나의 큐는 target 보다 클 것이고, 다른 하나는 target보다 작을 것이다.

 

그렇다면 큰 큐에서 popleft를 한 후 작은 큐에 append하면 된다.

 

이 과정에서 최대한 연산의 수를 줄여야한다.

그러려면 sum() 연산을 최대한 줄여야 한다.

 

 

따라서

1. sum 연산은 최초 두 큐의 합을 계산 할 때만 사용한다 ( 그래야 target값을 찾을 수 있기 때문)

2. while문 안에서의 sum() 연산을 피하기 위해 각각의 큐의 합을 생성해놓고, 단순연산으로 갱신하는 방법을 사용한다.