Java로 알고리즘 - [프로그래머스] 두 큐의 합 같게 만들기

원태연·2022년 8월 29일

Java algorithm

Algorithm문제

목록 보기

6/10

두 큐의 합 같게 만들기

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

문제

문제 내용

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

다음은 두 큐를 나타내는 예시입니다.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]
두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.
따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

제한사항

1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
1 ≤ queue1의 원소, queue2의 원소 ≤ 109
주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

입출력 예시

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

풀이

아이디어

문제가 너무나도 친절한 것 같다. 유심히 봐야할 대목은, 다음과 같다.

하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는...
두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다.
주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

위 대목을 집중적으로 고려하여 다음과 같은 전략을 세울 수 있다.

우선 pop, insert는 동일한 큐에서 이루어 질 수 없다. ex) [1, 2, 3] -> [2, 3, 1] 처럼 동일 큐 내에선 순서를 변경시키는 경우는 존재하지 않는다.

각 큐의 합이 정해져있다. 두 큐에 담긴 모든 원소의 합을 통해서 한 큐에 담긴 원소의 합을 알아낼 수 있다. 정답이 되는 합이 존재하기 때문에 수월하게 해결 할 수 있다.

위 예시처럼
queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]
인 경우 총 합은 30이고, 한 큐에 담긴 원소의 합은 15이어야 한다.

queue1의 현재 총 합은 14이고, queue2의 현재 총 합은 16이다.
그럼 당연하게도, queue2에서 pop()해서 queue1으로 insert() 연산을 수행 할 수 밖에 없다(최소 횟수를 구하므로)

Java에서 제공하는 Queue를 통해 구현해보자

필자는 Queue를 담고있는 새로운 객체를 생성했다. Queue의 sum을 자주 사용하게 되는데, ArrayDeque에서 sum()을 제공하지 않을 뿐더러, 매번 합을 구하는 것보단 상태로 저장함으로써 불필요한 연산을 줄일 수 있기 때문이다.

extends ArrayDeque<E>를 통해 상태만 저장해도 되지만,
int[]인 원시타입의 배열로 생성해야 한다는 점,
제공되는 add(), poll() 메서드 마다 상태를 변경해야 한다는 점 (어차피 override를 해야함)을 고려해서 새로운 객체를 생성했다.

class CustomQueue {
	Queue<Integer> integerQueue;
	long sumOfQueue; //문제에서 친절하게 주어진 대로 long 타입 사용

	public CustomQueue(int[] numArr) {
    //원시타입으로 주어진 배열을 Collections 인 Queue에 넣기 위함
		this.integerQueue = new ArrayDeque<>();
		for (int i = 0; i < numArr.length; i++) {
			int numData = numArr[i];
			sumOfQueue += numData; // 합 적용
			this.integerQueue.add(numData);
		}
	}

	public void popInsert(CustomQueue toQueue) { // 문제에선 하나의 연산으로 간주함
		Integer poll = this.integerQueue.poll();
		toQueue.integerQueue.add(poll);

		this.sumOfQueue -= poll; //상태 업데이트
		toQueue.sumOfQueue += poll; //상태 업데이트
	}

	public boolean checkEndCondition(CustomQueue toQueue) {
		if (this.sumOfQueue == toQueue.sumOfQueue) {
			return true;
		}

		return false;
	}
}

CustomQueue를 통해
원소의 합이 큰 큐에서 poll() 하고, 원소의 합이 작은 큐에 add()를 수행한다.

상태(합)이 역전되는 경우, swap을 통해 from to queue를 변경하면 된다.

class Solution {
	public int solution(int[] queue1, int[] queue2) {
		int answer = 0;

		//sum Of fromQueue > sum of toQueue
		CustomQueue fromQueue = new CustomQueue(queue1);
		CustomQueue toQueue = new CustomQueue(queue2);

		int limitCount = fromQueue.integerQueue.size() * 2;

		while (!fromQueue.checkEndCondition(toQueue)
			&& answer <= limitCount) {

			if (fromQueue.sumOfQueue < toQueue.sumOfQueue) {
				CustomQueue tmp = fromQueue;
				fromQueue = toQueue;
				toQueue = tmp;
			}

			fromQueue.popInsert(toQueue);
			answer += 1;
		}

		if (answer > limitCount) {
			return -1;
		}
		return answer;
	}
}

주의점

문제에선 합을 같게 만들 수 없는 경우, -1을 리턴해야 한다.
두 큐의 합이 같으면 이라는 종료조건에 걸리지 않는 경우이다.

그리디하게 작동하는 popInsert()의 연산이 돌고 돌아 다시 제자리로 온다면 만들 수 없다고 판단하면 된다. 그래서 큐의 size() * 2 번 만큼 돌아도 합이 다르다면 -1을 리턴하게 하려했다.
여기서 주의할 점은 size() * 2 번이 아니라 size() * 3으로 설정해야 한다.

예를 들어, [1,1,1,8,10,9], [1,1,1,1,1,1] 인 경우처럼 두 큐에서의 교환이 전부가 아니라, 한 큐가 비워진 뒤 그 큐를 채우고, 그 다음 다시 그리디하게 찾아가는 경우도 존재하기 때문이다.

EX)

[9] [1,1,1,1,1,1,1,1,1,8,10] (cnt = 5)

[9,1,1,1,1,1,1,1,1,1] [8, 10] (cnt = 5 + 9) => 14번

이 점들을 고려하여 해결하면 된다!!

정답 코드

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
	public int solution(int[] queue1, int[] queue2) {
		int answer = 0;

		//sum Of fromQueue > sum of toQueue
		CustomQueue fromQueue = new CustomQueue(queue1);
		CustomQueue toQueue = new CustomQueue(queue2);

		int limitCount = fromQueue.integerQueue.size() * 2;

		while (!fromQueue.checkEndCondition(toQueue)
			&& answer <= limitCount) {

			if (fromQueue.sumOfQueue < toQueue.sumOfQueue) {
				CustomQueue tmp = fromQueue;
				fromQueue = toQueue;
				toQueue = tmp;
			}

			fromQueue.popInsert(toQueue);
			answer += 1;
		}

		if (answer > limitCount) {
			return -1;
		}
		return answer;
	}
}

class CustomQueue {
	Queue<Integer> integerQueue;
	long sumOfQueue;

	public CustomQueue(int[] numArr) {
		this.integerQueue = new ArrayDeque<>();
		for (int i = 0; i < numArr.length; i++) {
			int numData = numArr[i];
			sumOfQueue += numData;
			this.integerQueue.add(numData);
		}
	}

	public void popInsert(CustomQueue toQueue) {
		Integer poll = this.integerQueue.poll();
		toQueue.integerQueue.add(poll);

		this.sumOfQueue -= poll;
		toQueue.sumOfQueue += poll;
	}

	public boolean checkEndCondition(CustomQueue toQueue) {
		if (this.sumOfQueue == toQueue.sumOfQueue) {
			return true;
		}

		return false;
	}
}