두 큐 합 같게 만들기(2022 KAKAO TECH INTERNSHIP) 문제
풀이 1.
queue1과 queue2의 각각의 합계를 계산하여 더 큰쪽의 값을 pop해서 더 작은쪽의 리스트에 넣어주는 방식으로 구상을 해 보았다. while문을 돌리면서 계속 계산을 해 주는데, 한번 돌 때마다 index를 1씩 증가시켜주고 index가 queue배열 길이의 2배를 돌게 되면 모두 다 순환한다고 생각하여 종료문을 작성해 주었다.
public int solution(int[] queue1, int[] queue2) {
int answer = Integer.MAX_VALUE;
// queue1의 0번째 인덱스부터 차례대로 뽑아서 queue2에 집어넣고 값 비교
// 만약 queue1의 모든 값이 더 크다면 queue1에서 값을 pop하여 queue2에 넣는다.
// 반대도 똑같이 진행 하면 최소 개수를 반환한다.
// 길이의 가변성을 위하여 배열을 콜렉션으로 바꿔준다.
List<Integer> list1 = Arrays.stream(queue1).boxed().collect(Collectors.toList());
List<Integer> list2 = Arrays.stream(queue2).boxed().collect(Collectors.toList());
// 먼저 두개의 합을 구하여서 더 큰 값의 queue의 원소를 pop한다.
int sum1 = Arrays.stream(queue1).sum();
int sum2 = Arrays.stream(queue2).sum();
int count = 0;
int index = 0;
while (index < queue1.length * 2) {
index++;
if (sum1 > sum2) {
int pop = list1.remove(0);
list2.add(pop);
} else {
int pop = list2.remove(0);
list1.add(pop);
}
count++;
sum1 = list1.stream().mapToInt(Integer::intValue).sum();
sum2 = list2.stream().mapToInt(Integer::intValue).sum();
if (sum1 == sum2) {
answer = Math.min(answer, count);
count = 0;
}
}
return answer == Integer.MAX_VALUE ? -1 : answer;
}풀이 1 실행결과
하지만 100점중에 20점 밖에 점수가 안나왔고, 어떤 부분이 문제인지 다시 생각을 해 보았다. sum1과 sum2를 stream을 다시 구하지 않고 pop을 한 값을 sum에 더해주거나 빼주는 것으로 변경해도 될 것 같다. 또한, 어차피 최소 값이 충족 되었을 때 while문을 빠져 나오게 되므로 그 이후의 count값은 안 구해도 되므로 count = 0으로 초기화 시켜주고 다시 반복해서 값을 구하는 과정이 필요 없을 것 같다. 또한, 문제를 자세히 읽어보니 sum을 구할 때 산술 오버플로우가 생길수도 있다고 했으므로 long타입으로 변환을 해 줘야 할 것이다.
풀이 2.
위의 생각들을 코드로 다시 옮겨 적어 보았다. list로 queue를 구현하던 것을 Queue자료구조로 다시 선언을 해 주고, sum은 long 타입으로 변환해 주었다. sum1과 sum2를 더해 중간값을 찾아주고 조건식에 넣어주는 방식으로 구현을 해 보았다.
public int solution(int[] queue1, int[] queue2) {
Queue<Integer> q1 = new ArrayDeque<>();
Queue<Integer> q2 = new ArrayDeque<>();
for (int num: queue1) q1.add(num);
for (int num: queue2) q2.add(num);
long sum1 = Arrays.stream(queue1).sum();
long sum2 = Arrays.stream(queue2).sum();
long mid = sum1 + sum2;
if (mid % 2 == 1) {
return -1;
}
mid /= 2;
int p1 = 0, p2 = 0, len = queue1.length * 2;
while (p1 <= len && p2 <= len) {
if (sum1 == mid) return p1 + p2;
if (sum1 > mid) {
int num = q1.poll();
sum1 -= num;
sum2 += num;
q2.add(num);
p1++;
} else {
int num = q2.poll();
sum1 += num;
sum2 -= num;
q1.add(num);
p2++;
}
}
return -1;
}풀이 2 실행결과
느낀점
구현과정을 세세하게 적어보고 생각한다음 코드로 옮기면 생각하는 시간이 길더라도 오히려 정작 코드를 치고 수정해 나가는 방식보다 짧을 것이라는 생각이 든다. 어차피 코딩테스트도 하나의 시험이라 정해진 시간이 있기 때문에, 구현에 앞서 모든 경우의 수를 잘 생각해보고 코드로 옮기는 습관을 잘 들여서 시간을 절약해야 겠다고 생각했다.
