[프로그래머스] 2022 KAKAO TECH INTERNSHIP - 두 큐 합 같게 만들기 (Java)

 

프로그래머스

 

풀이

큐를 이동시키기 전에 두 큐의 전체 합이 홀수이면 바로 -1을 리턴할 수 있다.

큐는 2개이지만 하나의 큐의 총합 == 전체 합 / 2 라면 원하는 값을 찾아낼 수 있기 때문에 한 개의 큐 값만 추적하면 된다.

 

한 가지 주의할 점이 있다면 원소를 몇 번까지 옮겨야 할 것인지에 대한 것이다.

일정 횟수를 초과하면 결국에는 반복이기 때문에 반복이 되기 전 탐색을 끊어내야 한다.

 

그 일정 횟수는 몇 번이어야 하는가?

1번 테스트 케이스의 실패 원인을 찾던 중 (큐의 크기) * 2 + 3 로 통과하긴 했지만, 예외 케이스가 있었다.

아래 케이스의 경우에는 2n + 4 번은 시도해야 통과하는 케이스였다.

 

 

 

프로그래머스 질문하기 채널에서도 이 횟수에 대한 의견이 분분했는데 육안으로 확인한 케이스로는 3n 정도면 적당하지 않을까 싶다.

 

코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    public int solution(int[] queue1, int[] queue2) {
        long sum1 = Arrays.stream(queue1).sum();
        long sum2 = Arrays.stream(queue2).sum();

        if ((sum1 + sum2) % 2 != 0) {
            return -1;
        }

        long targetSum = (sum1 + sum2) / 2;
        Queue<Integer> q1 = new LinkedList<>();
        Arrays.stream(queue1).forEach(q1::add);
        Queue<Integer> q2 = new LinkedList<>();
        Arrays.stream(queue2).forEach(q2::add);

        for (int i = 0; i < q1.size() * 3; i++) {
            if (sum1 == targetSum) {
                return i;
            }

            if (q1.isEmpty() || q2.isEmpty()) {
                break;
            }

            if (sum1 < targetSum) {
                int pop = q2.poll();
                sum2 -= pop;
                q1.add(pop);
                sum1 += pop;
                continue;
            }

            int pop = q1.poll();
            sum1 -= pop;
            q2.add(pop);
            sum2 += pop;
        }

        return -1;
    }
}