본문 바로가기

코테연습문제

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

from collections import deque

def solution(queue1, queue2):
    # 풀이과정 1
    q1, q2 = deque(queue1), deque(queue2)
    q1Sum, q2Sum = sum(q1), sum(q2)
    cnt = 0
    
    # 풀이과정 2, 3
    for _ in range(300000):
        if q1Sum < q2Sum:
            qElement = q2.popleft()
            q1.append(qElement)
            q1Sum += qElement
            q2Sum -= qElement
            cnt += 1

        elif q1Sum > q2Sum:
            qElement = q1.popleft()
            q2.append(qElement)
            cnt += 1
            q1Sum -= qElement
            q2Sum += qElement
        
        # 풀이과정 4
        else:
            return cnt
        
    return -1

유의했던 사항

1. 제한사항에서 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000 → for문의 범위를 300,000까지로 잡음

 

풀이과정

1. 두 큐를 deque로 하고, 두 큐에 담긴 모든 원소의 합을 구함

2. 두 큐 중 원소들의 합이 큰 큐에서 첫 원소를 pop(popleft) 한 후, 다른 큐에 append하고 cnt += 1

3. 두 큐의 각 원소들의 합이 같아질 때까지 2를 반복

4. 두 큐의 각 원소들의 합이 같아지면 return cnt, 아니면 return -1

 

알게된 것

1. deque

from collections import deque

보통 큐는 FIFO 방식으로, 선입선출을 원칙으로 한다. deque는 양방향 큐로, 앞과 뒤 양쪽 방향에서 원소를 추가/제거 할 수 있다. 또한 속도도 빠르다. 따라서 이 문제에서는 원소의 삽입/삭제의 과정을 여러번 반복해야하므로 삽입/삭제에 용이하고, 속도도 빠른 deque를 사용한다.

 


 

-) deque 사용

 

+) queue를 pop, append한 뒤 sum을 구해 비교한 값으로 문제 풀이 진행