두 큐 합 같게 만들기 (투 포인터)

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

 

 

문제 풀이

 큐 두 개로 투포인터를 구현하는 예제 같은 문제이다. 다른 알고리즘을 생각할 필요 없이 문제에서 제시하는 프로세스를 코드로 구현하면 된다. 라고 했지만 몇몇 테스트 케이스에서 시간 초과가 뜨고말았다. 구현한 코드가 O(N)이라고 생각했는데, 

 

처음에는 queue1의 배열이 원래와 같은 배열로 돌아오면 -1을 리턴하게 만들었는데, 몇몇 테스트 케이스에서 무한 루프가 발생했다.

시간 초과 테스트 케이스
q1: [10, 5, 1]
q2: [2, 2, 2]
answer: -1

 

 하나의 원소가 원래 자리로 돌아오는 값, 즉 작업의 최대값을 계산해보니까 아래와 같았다.

int maxCount = queue1.length + queue2.length + 2;

 

 이를 적용해서 코드를 짰더니 모든 테스트 케이스에서 정상작동되었다.

 

 

 

작성한 코드 (정답) 

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {

        int actCount = 0;

        Queue<Integer> q1 = new ArrayDeque<>();
        Queue<Integer> q2 = new ArrayDeque<>();

        long sumQ1 = 0;
        long sumQ2 = 0;
        int maxCount = queue1.length + queue2.length + 2;

        for (int i : queue1) {
            sumQ1 += i;
            q1.add(i);

        }
        for (int i : queue2) {
            sumQ2 += i;
            q2.add(i);
        }

        while (true) {

            if (actCount > maxCount || q1.isEmpty() || q2.isEmpty()) return -1;

            if (sumQ1 == sumQ2)
                return actCount;

            else if (sumQ1 < sumQ2) {
                int value = q2.peek();
                sumQ1 += value;
                sumQ2 -= value;
                q1.add(value);
                q2.remove();
            }

            else {
                int value = q1.peek();
                sumQ1 -= value;
                sumQ2 += value;
                q2.add(value);
                q1.remove();
            }

            actCount++;
        }
    }
}