(Java) 프로그래머스 - 두 큐 합 같게 만들기

처음에는 완전 탐색으로 구현해야 하나 생각했다.

그런데 생각해보니 매 실행마다 각 큐의 합계를 비교하면 답이 나올 것 같았다.

그래서 그리디 알고리즘을 사용해서 코드를 작성했다.

 

처음 작성한 코드는 실제로 큐를 2개 생성해서 삽입과 삭제를 반복하며 체크하는 로직이었다.

sumQ1나 sumQ2 값이 target 값과 같아질 때까지 while문을 돌린다.

그리고 q1Clone을 만들어서 q1이  처음과 같아지면 한 바퀴를 돌아도 답을 못 찾은 것이기 때문에

answer를 -1로 설정하고 탐색을 그만두게 했다.

그런데 이 코드는 테스트 케이스 11번에서 시간 초과로 계속 실패했다.

실제 queue에 삽입과 삭제를 반복하는데 시간이 꽤 걸렸던 것 같고

while문 조건을 변경하거나 break 조건을 만들면 통과될 것 같았는데 아무리 생각해도 생각이 나지 않아서

인덱스를 이용해서 다시 코드를 작성했다.

 

두 번째로 작성한 코드는 각 큐의 합을 구하고 list에 두 큐의 원소를 모두 집어넣는다.

그리고 첫 번째 큐의 idx와 두 번째 큐의 idx를 만들어 실제로 큐에 집어넣지 않고 비교할 수 있게 작성했다.

각 idx가 list.size를 벗어나면 queue1의 모든 원소가 queue2로 이동했거나 queue2의 모든 원소가 queue1로 이동했다는

뜻이기 때문에 답을 구할 수 없다는 게 된다.

 

두 번째로 작성한 코드가 처음 작성한 코드보다 수행 시간이 훨씬 빠르다.

 

---

실패 코드 (테스트 케이스 11번 시간 초과)

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) { 
        int answer = 0;
        long sumQ1 = 0;
        long sumQ2 = 0;
        Queue<Long> q1 = new LinkedList<>();
        Queue<Long> q2 = new LinkedList<>();

        // 두 큐의 합 구하고 실제 큐에 삽입
        for (int i = 0; i < queue1.length; i++) {
            sumQ1 += queue1[i];
            q1.add((long) queue1[i]);
            sumQ2 += queue2[i];
            q2.add((long) queue2[i]);
        }
		
        Queue<Long> q1Clone = new LinkedList<>(q1);

        long target = (sumQ1 + sumQ2) / 2;

        while (!(sumQ1 == target)) {
            long temp = 0;
            if(sumQ1 < sumQ2) {
                temp = q2.poll();
                q1.add(temp);
                sumQ2 -= temp;
                sumQ1 += temp;
            } else {
                temp = q1.poll();
                q2.add(temp);
                sumQ1 -= temp;
                sumQ2 += temp;
            }
            if(q1.equals(q1Clone)) {
                answer = -1;
                break;
            }
            answer++;
        }
        return answer;
    }
}

 

최종 코드

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) {   
        int answer = 0;

        // 각 큐의 합
        long sumQ1 = 0;
        long sumQ2 = 0;

        // 두 큐의 합 구하고 각 큐 원소 리스트에 추가
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < queue1.length; i++) {
            sumQ1 += queue1[i];
            sumQ2 += queue2[i];
            list.add(queue1[i]);
        }

        for (int i = 0; i < queue2.length; i++) {
            list.add(queue2[i]);
        }

        // 각 큐의 목표 합
        long target = (sumQ1 + sumQ2) / 2;
        // queue1의 idx 설정
        int queue1Idx = 0;
        // queue2의 idx 설정
        int queue2Idx = (queue1.length + queue2.length) / 2;

        while (!(sumQ1 == target)) {
            // mid와 start의 범위가 list.size를 벗어나면 원소 합을 같게 만들수 없음
            if(queue1Idx >= list.size() || queue2Idx >= list.size()) {
                answer = -1;
                break;
            }
            if (sumQ1 < sumQ2) {
                sumQ2 -= list.get(queue2Idx);
                sumQ1 += list.get(queue2Idx);
                queue2Idx++;
            } else {
                sumQ1 -= list.get(queue1Idx);
                sumQ2 += list.get(queue1Idx);
                queue1Idx++;
            }
            answer++;
        }
        return answer;
    }
}