PGS 두 큐 합 같게 만들기

URL

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

태그

그리디 알고리즘

문제 설명

•

길이가 같은 두 큐의 원소 합을 같게 만들기 위해 pop과 insert 작업을 최소 몇 번 해야 하는지 구하는 문제

예제 입력/출력

queue1	queue2	result
[3, 2, 7, 2]	[4, 6, 5, 1]	2
[1, 2, 1, 2]	[1, 10, 1, 2]	7
[1, 1]	[1, 5]	-1

제약 조건

•

1≤∣queue1∣=∣queue2∣≤300,0001 ≤ |queue1| = |queue2| ≤ 300,0001≤∣queue1∣=∣queue2∣≤300,000

◦

1≤1 ≤ 1≤ queue1의 원소, queue2의 원소 ≤109≤ 10^9≤109

문제 풀이

접근1 브루트 포스 - O(230만)O(2^{30만})O(230만)

접근2 그리디 - 상한 O(120만)O(120만)O(120만)

풀이 코드

from collections import deque

def solution(queue1, queue2):
    main_queue, sub_queue = deque(queue1), deque(queue2)
    total = sum(main_queue + sub_queue)

    if total % 2 == 1:
        return -1
    
    target = total // 2
    # 200만 번 그리디하게 시뮬레이션 수행
    main_sum = sum(main_queue)
    for cnt in range(0, int(2e6)):
        if main_sum == target:
            return cnt
        if main_sum < target:
            val = sub_queue.popleft()
            main_queue.append(val)
            main_sum += val
        else:
            val = main_queue.popleft()
            sub_queue.append(val)
            main_sum -= val
    
    return -1
Python
복사