두 큐 합 같게 만들기(카카오) 문제풀이

문제 

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

프로그래머스

 

 

 

문제 접근 방식

두 큐가 주어지며, 서로의 원소를 다른원소에 넣어가면서 두 큐의 합이 같도록 하는 최소 시행 횟수를 구하는 문제이다. 문제를 풀 때 고려해야할 사항은 크게 2가지이며, 이중 마지막 항목에 대해 어떻게 처리할지 몰라서 넘어갔다.

1. 어떤 큐에서 요소를 pop할 것인가?
>> 두 큐의 합이 다르다고 가정했을 때, 합이 같도록 하기 위해서는 합이 큰 큐에서 작은 큐로 요소를 옮겨줘야한다

2. 만약 합이 같도록 하는 방법이 없을 때 언제 끊어줄 것인가?
>> 이 부분을 어떻게 할지 몰라서 삽질하다가 넘겼다

>> (두 큐 길이의 합) *2 만큼 시행하면 모든 경우를 파악할 수 있다

 

 

시간 복잡도

(최대 두 큐 길이의 합) x 2 만큼을 선형 탐색하기 때문에 O(2N) 이 걸리며 N의 값이 최대 3e5 이기 때문에 시간 내에 동작한다.

 

 

코드

from collections import deque
def solution(queue1, queue2):
    s1,s2=sum(queue1),sum(queue2)
    q1=deque(queue1)
    q2=deque(queue2)
    count=0
    if s1==s2:
        return 0
    if (s1+s2)%2!=0:
        return -1
    
    size=(len(q1)+len(q2))*2
    for i in range(size):
        if s1==s2:
            return i
        elif s1>s2:
            v=q1.popleft()
            s1-=v
            q2.append(v)
            s2+=v
        else:
            v=q2.popleft()
            s2-=v
            q1.append(v)
            s1+=v
        
    return -1

 

 

회고

1. 언제까지 반복문을 돌릴지 모를 때, 상한선을 구하는 것도 방법이다
2. 파이썬의 경우 큐를 사용할 때, 일반 리스트보다는 deque를 사용하는 것이 효율적이다