성능 요약
-
메모리: 119 MB, 시간: 49.53 ms - Answer Code1
-
메모리: 98.7 MB, 시간: 4.72 ms - Answer Code2
구분
- 코딩테스트 연습 > 2022 KAKAO TECH INTERNSHIP
Answer Code1(2023.12.28)
import java.util.*;
class Solution {
public int solution(int[] queue1, int[] queue2) {
Queue<Integer> que1 = new LinkedList<>();
Queue<Integer> que2 = new LinkedList<>();
long sum1 = 0, sum2 = 0;
for(int i = 0; i < queue1.length; i++) {
sum1 += queue1[i];
que1.offer(queue1[i]);
}
for(int i = 0; i < queue2.length; i++) {
sum2 += queue2[i];
que2.offer(queue2[i]);
}
int count = 0;
while(sum1 != sum2) {
count++;
if(sum1 > sum2) {
int value = que1.poll();
sum1 -= value;
sum2 += value;
que2.offer(value);
} else {
int value = que2.poll();
sum1 += value;
sum2 -= value;
que1.offer(value);
}
if(count > (queue1.length + queue2.length) * 2) return -1;
}
return count;
}
}
문제풀이
-
각 큐의 합이 같을 때까지 반복문을 돌려줬다.
-
또한 원소의 합이 같지 않는 경우에는 return을 -1로 두는 특수 예외 조건이 존재한다.
-
분기 조건이
(queue1.length + queue2.length) * 2인 이유는 양쪽 큐 길이를 전부 돌았을 횟수로 잡았기 때문이다. -
즉, 각 큐에서 원소를 추출하고 집어넣는 작업이 최대로 반복될 수 있는 횟수를 고려한 것이다.
-
최악의 경우, 한 큐의 모든 원소를 다른 큐에 집어넣어야 할 수 있으므로, 이때 루프의 최대 횟수는 큐의 길이의 2배가 된다.
-
-
합계(sum)가 long 형으로 한 이유는
제한사항에서 queue1, queue2 원소의 최대 범위가 10^9이므로, 합 계산 과정 중 산술 오버플로우 발생 가능성이 있어서이다.
Answer Code2(2023.12.28)
import java.util.*;
class Solution {
public int solution(int[] queue1, int[] queue2) {
int[] totalQueue = new int[queue1.length + queue2.length];
long queue1Sum = 0;
long queue2Sum = 0;
for(int i = 0; i < queue1.length; i++) {
int val = queue1[i];
totalQueue[i] = val;
queue1Sum += val;
}
for(int i = queue1.length; i < queue1.length + queue2.length; i++) {
int val = queue2[i - queue1.length];
totalQueue[i] = val;
queue2Sum += val;
}
if((queue1Sum + queue2Sum) % 2 == 1) return -1;
int count = 0;
int left = 0;
int right = queue1.length;
long half = (queue1Sum + queue2Sum) / 2;
while(left < right && right < totalQueue.length) {
if(queue1Sum == half) {
return count;
} else if(queue1Sum > half) {
queue1Sum -= totalQueue[left++];
} else {
queue1Sum += totalQueue[right++];
}
count++;
}
return -1;
}
}
Review
-
두 번째 풀이는, 내가 푼게 아닌 다른 사람의 풀이를 가져왔다.
-
메모리와 시간을 비교했을 때, 시간 부분에서 약 10배 이상의 더 빠른 성능을 보여줬다. (49.53ms -> 4.72ms)
-
두 번째 코드에서는 배열의 크기에 대한 계산을 피하기 위해 left와 right 인덱스를 사용하여 배열을 순회하는 방식을 채택했다.
-
이는 배열의 크기에 상관없이 항상 효율적으로 작동할 수 있어서 더 빠른 성능을 보여준 것 같다.