<div id="readability-page-1" class="page"><div><h2 id="문제-설명">문제 설명</h2>
<a href="https://school.programmers.co.kr/learn/courses/30/lessons/118667">https://school.programmers.co.kr/learn/courses/30/lessons/118667</a>
<h2 id="풀이">풀이</h2>
기본적인 아이디어는 두 큐의 합이 같아질 때까지 합이 더 큰 큐에서 합이 더 작은 큐로 이동시켜준다는 것입니다.
예시로 주어진 아래 두 큐의 경우를 살펴보면 queue1의 합은 14, queue2의 합은 16입니다.
<pre><code>queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]</code></pre>
이때 합이 더 큰 쪽에서 합이 더 작은 쪽으로 이동시키는 알고리즘을 수행해보면,
<pre><code># round 1
queue1 = [3, 2, 7, 2, 4] # 18
queue2 = [6, 5, 1] # 12

# round 2
queue1 = [2, 7, 2, 4] # 15
queue2 = [6, 5, 1, 3] # 15</code></pre>
2번의 라운드를 거치고 나면 두 큐의 합이 같아지는 것을 알 수 있습니다.
우리는 각 큐에 직접 pop/insert를 수행하는 대신 두 큐의 합을 계속 추적하면서 각 큐의 시작 지점 인덱스를 옮겨주는 방식으로 구현하려고 합니다.
이런 방식을 투 포인터 (two pointer) 알고리즘이라고 하며, 두 큐에 직접 pop/insert를 수행하는 것보다 더 효율적입니다.
<pre><code>queue = [3, 2, 7, 2, 4, 6, 5, 1]

L = 0, LSum = 14
R = 4, RSum = 16</code></pre>
queue1과 queue2 두 개를 합친 새로운 큐, queue를 만든 뒤 각 큐의 시작 지점을 L, R로 선언하고 각각의 합을 구해줬습니다.
이제 각 라운드를 진행하고 나면 어떻게 되는지 살펴봅시다.
<pre><code># round 1
# queue2에서 pop한 뒤, queue1에 insert해주는 것은 마치 R 포인터를 오른쪽으로 하나 옮기는 것과 동일합니다.
L = 0, LSum = 18
R = 5, RSum = 12

# round 2
# queue1의 합이 더 크므로 queue1에서 pop한 뒤, queue2로 insert 해줬습니다.
# 이는 L 포인터를 오른쪽으로 하나 옮기는 것과 같습니다.
L = 1, LSum = 15
R = 5, RSum = 15</code></pre>
여기서 조심해줘야되는 부분은 L 혹은 R 포인터를 이동시킬 때 queue의 길이를 벗어날 수 있다는 점입니다. 
그러므로 포인터를 이동시킬 때 항상 queue의 길이만큼 mod를 취해줘서 값이 올바른 범위를 벗어나지 않도록 해줘야 합니다.
이제 코드를 살펴보겠습니다.
<pre><code>public int solution(int[] queue1, int[] queue2) {
 int N = queue1.length;

 int[] queue = new int[2 * N];
 System.arraycopy(queue1, 0, queue, 0, N);
 System.arraycopy(queue2, 0, queue, N, N);

 long LSum = 0;
 for (int i : queue1) {
 LSum += i;
 }

 long RSum = 0;
 for (int i : queue2) {
 RSum += i;
 }

 int L = 0;
 int R = N;

 int moves = 0;

 while (moves &lt;= 4 * N) {
 if (LSum == RSum) {
 return moves;
 } else if (LSum &gt; RSum) {
 LSum -= queue[L];
 RSum += queue[L];

 L = (L + 1) % queue.length;
 } else {
 LSum += queue[R];
 RSum -= queue[R];

 R = (R + 1) % queue.length;
 }

 moves++;
 }

 return -1;
 }</code></pre>
코드를 순서대로 살펴보면
<ol>
<li>두 큐를 합친 새로운 큐, <code>queue</code>를 만들어줍니다.</li>
<li>이전 큐의 합, <code>LSum</code>과 <code>RSum</code>을 구합니다.</li>
<li>큐의 합을 비교하여, 포인터를 이동시키는 연산을 수행합니다. 이때 위에서 말했듯이 전체 큐의 길이 범위를 벗어나지 않도록 mod를 취해줍니다.</li>
</ol>
<h2 id="시간공간-복잡도">시간/공간 복잡도</h2>
시간 복잡도의 경우 worst case에 4 N 만큼의 연산을 수행하므로 O(N)이 됩니다. (N은 큐의 길이) 
공간 복잡도의 경우 <code>queue</code>를 생성하기 위해 2 N 만큼의 공간을 사용하므로 역시 O(N)이 됩니다.</div></div>

leejh3224.log

문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/118667
풀이
기본적인 아이디어는 두 큐의 합이 같아질 때까지 합이 더 큰 큐에서 합이 더 작은 큐로 이동시켜준다는 것입니다.
예시로 주어진 아래 두 큐의 경우를 살펴보면 queue1의 합은 14, queue2의 합은 16입니다.
queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]
이때 합이 더 큰 쪽에서 합이 더 작은 쪽으로 이동시키는 알고리즘을 수행해보면,
# round 1
queue1 = [3, 2, 7, 2, 4] # 18
queue2 = [6, 5, 1] # 12
# round 2
queue1 = [2, 7, 2, 4] # 15
queue2 = [6, 5, 1, 3] # 15
2번의 라운드를 거치고 나면 두 큐의 합이 같아지는 것을 알 수 있습니다.
우리는 각 큐에 직접 pop/insert를 수행하는 대신 두 큐의 합을 계속 추적하면서 각 큐의 시작 지점 인덱스를 옮겨주는 방식으로 구현하려고 합니다.
이런 방식을 투 포인터 (two pointer) 알고리즘이라고 하며, 두 큐에 직접 pop/insert를 수행하는 것보다 더 효율적입니다.
queue = [3, 2, 7, 2, 4, 6, 5, 1]
L = 0, LSum = 14
R = 4, RSum = 16
queue1과 queue2 두 개를 합친 새로운 큐, queue를 만든 뒤 각 큐의 시작 지점을 L, R로 선언하고 각각의 합을 구해줬습니다.
이제 각 라운드를 진행하고 나면 어떻게 되는지 살펴봅시다.
# round 1
# queue2에서 pop한 뒤, queue1에 insert해주는 것은 마치 R 포인터를 오른쪽으로 하나 옮기는 것과 동일합니다.
L = 0, LSum = 18
R = 5, RSum = 12
# round 2
# queue1의 합이 더 크므로 queue1에서 pop한 뒤, queue2로 insert 해줬습니다.
# 이는 L 포인터를 오른쪽으로 하나 옮기는 것과 같습니다.
L = 1, LSum = 15
R = 5, RSum = 15
여기서 조심해줘야되는 부분은 L 혹은 R 포인터를 이동시킬 때 queue의 길이를 벗어날 수 있다는 점입니다.
그러므로 포인터를 이동시킬 때 항상 queue의 길이만큼 mod를 취해줘서 값이 올바른 범위를 벗어나지 않도록 해줘야 합니다.
이제 코드를 살펴보겠습니다.
public int solution(int[] queue1, int[] queue2) {
 int N = queue1.length;
 int[] queue = new int[2 * N];
 System.arraycopy(queue1, 0, queue, 0, N);
 System.arraycopy(queue2, 0, queue, N, N);
 long LSum = 0;
 for (int i : queue1) {
 LSum += i;
 }
 long RSum = 0;
 for (int i : queue2) {
 RSum += i;
 }
 int L = 0;
 int R = N;
 int moves = 0;
 while (moves <= 4 * N) {
 if (LSum == RSum) {
 return moves;
 } else if (LSum > RSum) {
 LSum -= queue[L];
 RSum += queue[L];
 L = (L + 1) % queue.length;
 } else {
 LSum += queue[R];
 RSum -= queue[R];
 R = (R + 1) % queue.length;
 }
 moves++;
 }
 return -1;
 }
코드를 순서대로 살펴보면
두 큐를 합친 새로운 큐, queue를 만들어줍니다.
이전 큐의 합, LSum과 RSum을 구합니다.
큐의 합을 비교하여, 포인터를 이동시키는 연산을 수행합니다. 이때 위에서 말했듯이 전체 큐의 길이 범위를 벗어나지 않도록 mod를 취해줍니다.
시간/공간 복잡도
시간 복잡도의 경우 worst case에 4 * N 만큼의 연산을 수행하므로 O(N)이 됩니다. (N은 큐의 길이)
공간 복잡도의 경우 queue를 생성하기 위해 2 * N 만큼의 공간을 사용하므로 역시 O(N)이 됩니다.

두 큐 합 같게 만들기

댓글