[Programmers] 두 큐 합 같게 만들기 - python

[Programmers] 두 큐 합 같게 만들기 - 파이썬

 

🎈문제

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

프로그래머스

 

💬설명

1. 각 배열을 deque에 넣어서 큐로 만든다.
2. 만약 sum 이 홀수 인 경우 어떻게 해도 반반 나눠질 수 없으니 예외 처리해준다.
   • 주의점: sum같은 경우는 while문 안에서 돌리는 것보다 밖에서 sum을 미리 구한 뒤, 내부에서 + - 정도만 해주는게 효율적이다.
3. 이후에 while문 안에서 합이 큰 큐에서 합이 작은 큐로 원소가 넘어갈 수 있도록 sum을 따로 더하고 빼주며 반복한다.
4. 만약 반복 회수가 큐의 길이의 4배와 같아지면 이 케이스는 반으로 나눠질 수 없으니 -1을 리턴

 

[카카오 코딩테스트 공식 해설]

https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

문제에서 요구하는 것은 queue1과 queue2의 원소 합을 같게 만드는 것입니다. 처음 주어진 queue1의 합을 L, queue2의 합을 R이라고 했을 때, L과 R을 같게 만들기 위해서는 다음과 같은 탐욕법을 사용하여 해결할 수 있습니다.
 
L > R이라면, queue1의 원소를 queue2로 넘겨줍니다.L < R이라면, queue2의 원소를 queue1로 넘겨줍니다.
 
위 방법이 왜 유효한지 간단하게 증명하면 다음과 같습니다.
앞에서 설명한 방식과 반대로 L > R인 상황에서 먼저 L을 증가시키고 R을 감소시키는 방법이 최적인 경우가 있다고 가정하겠습니다. 이 경우 L = R을 만들기 위해서는 언젠가 L을 감소시키고 R을 증가시켜야 하고, 결국 queue1의 원소를 queue2로 넘겨주는 동작은 반드시 필요합니다. queue2의 원소를 queue1으로 넘겨준 이후에 queue1의 원소를 queue2로 넘겨주든, 이 순서를 반대로 하든 결과는 동일하기 때문에, L > R인 상황에서 L을 감소시키는 방법은 항상 최적이 될 수 있습니다.
이때, 직접 큐(Queue) 자료구조를 이용하지 않고 단순히 배열을 큐로 사용하면 0번 원소를 지우는 과정에서 시간 초과가 발생할 수도 있습니다.
이 방법 이외에도, 각 큐의 원소를 실제로 이동시키지 않고 한 구간의 시작 위치와 끝 위치를 포인터로 지정하여 이동하는 투 포인터(Two Pointers) 방식의 풀이도 존재합니다.
먼저 queue1을 왼쪽, queue2를 오른쪽에 이어 붙이고 하나의 배열처럼 본다고 생각해 봅시다. 이 경우 각 큐에 pop 또는 insert 연산을 하는 것은 배열의 경계를 이동시키거나 맨 앞의 원소를 맨 뒤에 이동시키는 연산을 하는 것이라고 볼 수 있으므로, 각 큐는 이렇게 정의한 배열에서 연속된 구간의 원소로만 이루어진다고 생각할 수 있습니다. 이 상황에서 queue1의 시작과 끝을 나타내는 두 포인터를 적절히 이동시키는 것입니다.
각 큐의 원소의 합은 (L + R) / 2가 되어야 하므로, queue1의 두 포인터 내에 있는 모든 원소의 합이 (L + R) / 2보다 작을 땐 끝 위치를 가리키는 포인터를 이동시키고 (L + R) / 2보다 클 땐 시작 위치를 가리키는 포인터를 이동시키면 됩니다.
이때, 전체 배열의 길이가 2n이므로, 한 포인터 당 최대 2n번의 이동이 필요합니다. 따라서, 총 4n만큼의 작업을 수행한 뒤에도 두 큐의 합을 같게 만들지 못했다면 그 이후에는 이미 탐색했던 구간을 다시 탐색하는 것이므로 의미가 없습니다. 이 경우에는 -1을 반환합니다.

 

👩‍💻코드

from collections import deque


def solution(queue1, queue2):
    answer = 0
    
    q1 = deque(queue1)
    q2 = deque(queue2)
    
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    
    # 홀수인 경우
    if (sum1 + sum2) % 2 != 0:
        return -1
    
    while True:
        if answer == 4 * len(queue1):
            return -1
        
        if sum1 > sum2:
            value = q1.popleft()
            q2.append(value)
            sum1 -= value
            sum2 += value
        elif sum1 < sum2:
            value = q2.popleft()
            q1.append(value)
            sum1 += value
            sum2 -= value
        else:
            return answer
        answer += 1