내일은 알고리즘

https://nodingco.tistory.com/135

Python 풀이를 Java로 옮기기만 했습니다. 문제링크와 아이디어, 구현 방법은 위 링크에 설명되어 있습니다.

import java.util.LinkedList;
import java.util.Queue;

public class q118667_Programmers_두큐합같게만들기 {
	public static void main(String[] args) {

		System.out.println(solution(new int[] { 3, 2, 7, 2 }, new int[] { 4, 6, 5, 1 }));

	}

	static int solution(int[] queue1, int[] queue2) {
		Queue<Long> leftqueue = new LinkedList<Long>();
		Queue<Long> rightqueue = new LinkedList<Long>();
		long leftsum = 0;
		long rightsum = 0;
		int count = 0;
		int limit = 2 * (queue1.length + queue2.length);

		for (int i = 0; i < queue1.length; i++) {
			leftsum += queue1[i];
			leftqueue.add((long) queue1[i]);
		}
		for (int i = 0; i < queue2.length; i++) {
			rightsum += queue2[i];
			rightqueue.add((long) queue2[i]);
		}

		if ((leftsum + rightsum) % 2 == 1) {
			return -1;
		}

		while (count < limit) {
			if (leftsum == rightsum) {
				return count;
			}

			if (leftsum < rightsum) {
				leftsum += rightqueue.peek();
				rightsum -= rightqueue.peek();
				leftqueue.add(rightqueue.poll());
			} else {
				rightsum += leftqueue.peek();
				leftsum -= leftqueue.peek();
				rightqueue.add(leftqueue.poll());
			}
			count += 1;
		}

		return -1;

	}
}

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

두 큐의 합을 같게 만드는 문제입니다.

그리디 하게 합이 더 큰 쪽의 큐에서 수를 빼서 작은 쪽으로 넣으면 되는데, 이유는 조금만 생각해봐도 떠올릴 수 있습니다.

(큐의 선입선출 구조를 생각하시면 왜 그리디하게 풀이해서 정답이 나오는지 알 수 있습니다.)

입력된 리스트를 두개의 큐에 (Python의 경우 deque) 담고 그리디 하게 값을 빼고 넣어주며 같은 값이 되게 해 주면 됩니다.

실행시간을 단축시키는 가지치기가 몇개 가능한데, 우선 두 큐의 합을 더한 값이 홀수면 어떤 방법을 써도 같게 만들 수가 없습니다. 3을 정수로 2등분 시키는 게 불가능하듯이요.

2로 나눈 나머지가 0이 아니면 -1을 리턴하시면 됩니다. 그리고 큐의 합을 매번 구하지 않도록 초기 상태에서 합을 미리 구해놓은 다음, 옮기는 수만 합에서 직접 빼고 더해주면 매번 큐의 합을 구하는 것보다 빠르게 동작할 수 있습니다.

from collections import deque


def solution(queue1, queue2):
    left = sum(queue1)
    lqueue = deque(queue1)
    right = sum(queue2)
    rqueue = deque(queue2)
    limit = 2 * (len(queue1) + len(queue2))
    count = 0

    if (left + right) % 2 == 1:
        return -1

    while count < limit:

        if left == right:
            return count

        if left < right:
            gap = rqueue.popleft()
            left += gap
            right -= gap
            lqueue.append(gap)
        else:
            gap = lqueue.popleft()
            right += gap
            left -= gap
            rqueue.append(gap)

        count += 1
    return -1


print(solution([3, 2, 7, 2], [4, 6, 5, 1]))