프로그래머스 | Level 2 | 두 큐 합 같게 만들기
Programmers | Level 2 | 두 큐 합 같게 만들기
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Greedy
Description
길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(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 해주세요.
Constraints
- 1 ≤
queue1의 길이 =queue2의 길이 ≤ 300,000 - 1 ≤
queue1의 원소,queue2의 원소 ≤ 1,000,000,000 - 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.
Examples
| queue1 | queue2 | return |
|---|---|---|
[3, 2, 7, 2] | [4, 6, 5, 1] | 2 |
[1, 2, 1, 2] | [1, 10, 1, 2] | 7 |
[1, 1] | [1, 5] | -1 |
Solutions
Code
import java.util.*;
class Solution {
public int solution(int[] queue1, int[] queue2) {
Deque<Integer> q1 = new LinkedList<>(); // 첫 번째 큐를 저장할 Deque
Deque<Integer> q2 = new LinkedList<>(); // 두 번째 큐를 저장할 Deque
long sum1 = 0; // 첫 번째 큐의 원소 합
long sum2 = 0; // 두 번째 큐의 원소 합
// 첫 번째 큐를 초기화하고 합을 계산
for (int number : queue1) {
q1.offer(number);
sum1 += number;
}
// 두 번째 큐를 초기화하고 합을 계산
for (int number : queue2) {
q2.offer(number);
sum2 += number;
}
long total = sum1 + sum2; // 두 큐의 전체 합을 계산
if (total % 2 != 0) return -1; // 전체 합이 홀수면 두 큐를 같게 만들 수 없으므로 -1 반환
int count = 0; // 작업 횟수 초기화
// 두 큐의 원소를 이동시키며 합을 맞추는 과정
while (count <= queue1.length * 4) { // 큐의 최대 길이의 4배까지 반복
if (sum1 == sum2) return count; // 두 큐의 합이 같아지면 작업 횟수 반환
count++; // 작업 횟수 증가
if (sum1 > sum2) {
// 첫 번째 큐의 합이 더 크면 첫 번째 큐에서 원소를 추출하여 두 번째 큐에 추가
int head = q1.poll(); // 첫 번째 큐의 앞에서 원소 추출
q2.offer(head); // 두 번째 큐의 뒤에 원소 추가
sum1 -= head; // 첫 번째 큐의 합에서 추출한 원소의 값을 빼기
sum2 += head; // 두 번째 큐의 합에 추출한 원소의 값을 더하기
} else {
// 두 번째 큐의 합이 더 크면 두 번째 큐에서 원소를 추출하여 첫 번째 큐에 추가
int head = q2.poll(); // 두 번째 큐의 앞에서 원소 추출
q1.offer(head); // 첫 번째 큐의 뒤에 원소 추가
sum1 += head; // 첫 번째 큐의 합에 추출한 원소의 값을 더하기
sum2 -= head; // 두 번째 큐의 합에서 추출한 원소의 값을 빼기
}
}
return -1; // 최대 작업 횟수를 초과하면 -1 반환
}
}
Approach
이 문제는 두 큐의 원소 합을 같게 만들기 위해 최소한의 원소 이동 작업을 수행하는 문제입니다. 이를 해결하기 위해서는 그리디 알고리즘과 큐(Queue)의 특성을 이해하는 것이 중요합니다. 각 큐의 합이 같아지도록 원소를 이동시키는 과정을 설계하는 데 중점을 두어야 합니다.
1. 문제 분석
이 문제는 두 개의 동일한 길이를 가진 큐에서 원소를 주고받아 각 큐의 원소 합을 같게 만드는 최소 작업 횟수를 구하는 문제입니다. 이를 해결하기 위해 큐의 특성과 문제에서 요구하는 접근 방법을 이해하는 것이 중요합니다.
- Queue: FIFO(First In, First Out) 구조로, 먼저 들어온 원소가 먼저 나가는 형태입니다. 이 문제에서는 배열의 맨 앞에 있는 원소를 추출하고, 다른 큐의 맨 뒤에 추가하는 작업을 통해 두 큐의 합을 동일하게 만들려 합니다. 이러한 구조적 특성은 원소를 효율적으로 이동시키는 데 중요한 역할을 합니다.
- 원소의 이동 방향: 두 큐의 합이 더 큰 큐에서 작은 큐로 이루어지며, 이 과정을 통해 두 큐의 합을 점진적으로 같게 만드는 것이 목표입니다.
- 최소 조건: 두 큐의 원소 합이 같아지기 위해서는 두 큐의 전체 합이 반드시 짝수여야 합니다. 두 큐의 원소 합이 같아지려면, 합쳐진 큐의 총합을 반으로 나눈 값이 정수여야 하며, 이는 곧 전체 합이 짝수여야만 가능하다는 것을 의미합니다. 만약 전체 합이 홀수라면, 두 큐의 합을 같게 만드는 것은 불가능하며, 이 경우 바로
-1을 반환할 수 있습니다. - 최대 작업 횟수: 주어진 큐의 길이를
n이라고 할 때, 각 큐의 원소를 최대n - 1번까지 이동시킬 수 있습니다. 이 문제에서는 주어지는 두 큐가 동일한 원소n개를 가지기 때문에, 최악의 경우 두 큐의 원소를 합쳐4n번의 이동이 필요할 수 있습니다. 이는 큐의 원소가 지속적으로 다른 큐로 이동하면서 결과적으로 원래 상태로 돌아가는 경우를 포함하기 때문입니다. 따라서 최대 작업 횟수는 일반적으로n * 4으로 설정하며, 이 범위를 초과하면 어떤 경우에도 두 큐의 합을 같게 만들 수 없는 상황으로 판단하고-1을 반환합니다.
그리디 알고리즘은 문제를 해결할 때 각 단계에서 최선의 선택을 하는 전략입니다. 이 문제에서는 현재 두 큐의 합을 비교하여, 합이 더 큰 큐에서 작은 큐로 원소를 이동시키는 것이 최선의 선택입니다. 이렇게 함으로써 두 큐의 합을 가능한 한 빨리 같게 만들 수 있습니다. 이 과정에서 매번 가장 합리적인 선택을 통해 전체 작업 횟수를 최소화합니다.
2. 접근 방식
이 문제는 그리디 알고리즘을 사용하여 큐의 원소를 반복적으로 이동시키면서 최소 작업 횟수를 찾는 방식으로 접근할 수 있습니다.
- 각 큐의 초기 합 계산: 먼저 주어진 두 큐의 초기 합을 계산하고, 두 큐의 전체 합이 짝수인지 확인합니다.
- 큐의 원소 이동: 두 큐의 합이 같아질 때까지, 합이 큰 큐에서 작은 큐로 원소를 이동시키는 작업을 반복합니다. 이 과정에서 큐의 특성을 고려해 가장 앞에 있는 원소를 추출하여 이동시킵니다.
3. 큐 구현과 초기화
이 단계에서는 주어진 두 배열을 큐 구조로 변환하고, 각 큐의 원소 합을 계산하여 초기 상태를 설정합니다. 이를 통해 큐의 데이터를 FIFO 방식으로 처리하며, 각 큐의 합을 지속적으로 추적할 수 있습니다.
// 첫 번째 큐와 두 번째 큐를 저장할 Deque 객체를 생성합니다.
Deque<Integer> q1 = new LinkedList<>();
Deque<Integer> q2 = new LinkedList<>();
// 첫 번째 큐와 두 번째 큐의 합을 저장할 변수를 선언합니다.
long sum1 = 0;
long sum2 = 0;
// 주어진 배열 queue1의 모든 원소를 q1에 추가하고, sum1에 각 원소를 더하여 큐의 합을 초기화합니다.
for (int number : queue1) {
q1.offer(number); // 큐의 뒤에 원소를 추가합니다.
sum1 += number; // 큐의 합에 현재 원소를 더합니다.
}
// 주어진 배열 queue2의 모든 원소를 q2에 추가하고, sum2에 각 원소를 더하여 큐의 합을 초기화합니다.
for (int number : queue2) {
q2.offer(number); // 큐의 뒤에 원소를 추가합니다.
sum2 += number; // 큐의 합에 현재 원소를 더합니다.
}
- 큐 구현: 주어진 배열
queue1과queue2를 각각Deque로 변환하여, 큐의 특성을 유지하면서 원소들을 관리합니다.Deque<T>은 양쪽 끝에서 삽입과 삭제가 가능한 자료 구조로, 이 문제에서 필요한 큐 연산을 효율적으로 처리할 수 있습니다. - 초기 합 계산: 각 큐의 원소를 큐에 추가하면서 동시에 초기 합을 계산합니다. 이 초기 합은 이후 큐의 균형을 맞추는 과정에서 중요한 역할을 합니다. 큐의 모든 원소의 합이
int타입을 초과할 수 있으므로,long타입을 사용하여 안정적으로 합을 관리합니다. 이 값들은 두 큐의 상태를 비교하고 조정하는 데 사용됩니다.
4. 그리디 접근을 사용한 큐의 원소 이동
이 부분에서는 두 큐의 합이 같아지도록 그리디 알고리즘을 사용하여 원소를 이동시키는 과정을 구현합니다. 현재 합이 더 큰 큐에서 작은 큐로 원소를 이동시키면서, 각 큐의 합이 같아질 때까지 반복적으로 비교하고 조정합니다.
int count = 0; // 원소 이동 횟수를 기록할 변수 초기화
int max = queue1.length * 4; // 최대 이동 가능 횟수를 설정
// 두 큐의 합이 같아지거나 최대 이동 횟수를 초과할 때까지 반복
while (count <= max) {
// 두 큐의 합이 같아진 경우, 현재까지의 이동 횟수를 반환하고 종료
if (sum1 == sum2) return count;
// 이동 횟수 증가
count++;
// 첫 번째 큐의 합이 더 큰 경우, 첫 번째 큐에서 원소를 꺼내 두 번째 큐에 추가
if (sum1 > sum2) {
int head = q1.poll(); // 첫 번째 큐에서 가장 앞의 원소를 꺼냅니다.
q2.offer(head); // 꺼낸 원소를 두 번째 큐의 뒤에 추가합니다.
sum1 -= head; // 첫 번째 큐의 합에서 꺼낸 원소의 값을 뺍니다.
sum2 += head; // 두 번째 큐의 합에 꺼낸 원소의 값을 더합니다.
// 두 번째 큐의 합이 더 큰 경우, 두 번째 큐에서 원소를 꺼내 첫 번째 큐에 추가
} else {
int head = q2.poll(); // 두 번째 큐에서 가장 앞의 원소를 꺼냅니다.
q1.offer(head); // 꺼낸 원소를 첫 번째 큐의 뒤에 추가합니다.
sum1 += head; // 첫 번째 큐의 합에 꺼낸 원소의 값을 더합니다.
sum2 -= head; // 두 번째 큐의 합에서 꺼낸 원소의 값을 뺍니다.
}
}
- 최대 이동 횟수 설정: 최악의 경우를 고려하여 최대 이동 횟수를
queue1.length * 4로 설정합니다. 이는 두 큐의 원소를 모두 한 번씩 이동시키는 과정에서 발생할 수 있는 최대 시도 횟수입니다. 이 이상의 이동이 발생한다면, 두 큐의 합이 같아지지 않는다고 판단할 수 있습니다. - 합 비교 및 원소 이동: 현재 각 큐의 합을 비교한 후, 더 큰 합을 가진 큐에서 작은 큐로 원소를 이동시킵니다. 이때 원소를 이동시키면서, 이동된 원소의 값을 해당 큐의 합에서 빼고, 반대 큐의 합에 더하여 합의 균형을 맞춥니다.
- 종료 조건: 두 큐의 합이 같아지는 경우 반복문을 종료하고, 그동안의 이동 횟수를 반환합니다.
5. 결과 반환
만약 최대 횟수를 초과하도록 큐의 합이 같아지지 않는 경우, 이는 불가능한 상황이므로 -1을 반환하여 불가능함을 나타냅니다.
// 최대 이동 횟수를 초과했음에도 두 큐의 합이 같아지지 않은 경우, `-1` 반환
return -1;
Complexity
- ⏳ TC: O(n)
- 💾 SC: O(n)
각 큐의 길이를 n이라고 할 때, 원소를 최대 4n번 이동시킬 수 있으므로, 시간 복잡도는 O(n)입니다. 또한, 큐를 저장하기 위한 추가적인 공간이 필요하기 때문에 공간 복잡도도 O(n)입니다. 이 알고리즘은 큐의 기본 동작과 그리디 전략을 조합하여 문제를 효율적으로 해결합니다. 핵심은 큐의 특성과 주어진 조건을 잘 활용하여 최적의 방법으로 문제에 접근하는 것입니다.
- Algorithm
- Greedy