[KAKAO, python] 두 큐 합 같게 만들기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=python3

프로그래머스

말 그대로 두 큐의 합을 같게 만드는 것이다.

 

문제를 처음 봤을 때는 완탐으로 푸나 싶었지만, 제한 사항에서도 알 수 있듯이 완탐으로 풀면 시간 초과 난다.

그리고 완탐으로 푸는 방법도 생각이 잘... 나지 않는다.

 

사실 문제를 단순하게 접근하면 어느 정도는 푸는 문제다. 하지만, 같게 만들 수 없을 때 '-1'을 반환하는 것과 파이썬으로 풀 경우 자료구조의 시간 초과 고려를 해줘야 한다. 

문제 풀이

첫 번째 예시로 설명을 해보자면 일단 두 큐의 합을 각각 구해보자.

그럼 첫 큐의 합은 14이고 두 번째 큐의 합은 16이다.

여기서 중요한 건 위의 값들을 큐로 고려해줘야 한다는 것이다. 그러므로 합이 큰 두 번째 큐에서 첫 원소를 꺼내서 첫 번째 큐에 넣어준다.

그러면 첫 큐의 합은 18이 되고 두 번째 큐의 합은 12가 된다.

그러면 합이 더 큰 첫 큐에서 첫 번째 원소를 꺼내 두 번째 원소에 넣어주자.

그러면 합은 첫 큐가 15이고 두 번째 큐가 15가 되서 같아진다.

그러므로 최소 이동 수는 2가 된다.

 

위의 설명대로 풀면 되는데, 중요한 건 바로 합을 같게 만들 수 없는 경우이다.

예를 들어서 [1, 1]과 [1, 2]가 있다고 해보자.

그러면 1이 자꾸만 왔다갔다 해서 답은 안 나오고 시간 초과만 될 것이다.

그러므로 count의 한계를 큐들의 최대 길이인 300,000으로 잡아서 시간 초과를 막아야 한다.

 

또한 파이썬으로 풀 경우 큐의 자료 구조를 deque()로 해줘야 한다.

나는 처음에 그냥 list에다가 .pop(0)을 했는데, list를 쓰면 값을 뺄 때마다 O(n)만큼의 시간이 걸린다. 그러므로 큐로 값을 뺄 때 O(1)의 시간 복잡도를 가지는 deque()를 사용해줘야 한다!

 

여담이지만 투 포인터로도 풀 수 있을 거 같다.

코드

from collections import deque

def make_target(sum1, sum2, queue1, queue2):
    count = 0
    q1 = deque(queue1)
    q2 = deque(queue2)
    while sum1 != sum2:
        if count == 300000:
            count = -1
            break
        #print(f'{sum1} {sum2}')
        if sum1 > sum2:
            tmp = q1.popleft()
            q2.append(tmp)
            sum1 -= tmp
            sum2 += tmp
        elif sum1 < sum2:
            tmp = q2.popleft()
            q1.append(tmp)
            sum2 -= tmp
            sum1 += tmp
        count += 1
    return count


def solution(queue1, queue2):
    answer = -2
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    sum_all = (sum1+sum2)
    if sum_all%2 != 0:
        return -1

    return make_target(sum1, sum2, queue1, queue2)