프로그래머스 lv2 두 큐 합 같게 만들기

문제 링크

두 큐 합 같게 만들기

풀이

• 매 순간에 각 큐의 누적합의 크기를 비교해서 누적합이 큰 쪽에서 poll하고, 적은쪽에 add해준다.
• 그리고 그 순간마다 cnt를 누적해서 총 횟수를 구한다.

import java.util.LinkedList;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        LinkedList<Integer> q1 = new LinkedList<>();
        LinkedList<Integer> q2 = new LinkedList<>();

        // initialize
        for (int i = 0; i < queue1.length; i++) {
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }

		// 횟수
        int cnt = 0;
        
        // 누적합
        long sum1 = getSum(q1);
        long sum2 = getSum(q2);
        
        // 두 배열 원소들의 합을 나누기 2했을때 나머지가 1이면 결국 각 큐의 원소 합을 같게 만들 수 없다.
        if((sum1 + sum2) % 2 == 1) return -1;
        
        // 큐 한쪽이 작으면 큰 쪽에서 뽑아서 넣기.
        while (cnt < (queue1.length * 3)) {
            if (sum1 > sum2) {
                Integer poll = q1.poll();
                q2.add(poll);
                sum1 -= poll;
                sum2 += poll;
                cnt++;
            } else if (sum2 > sum1) {
                Integer poll = q2.poll();
                q1.add(poll);
                sum2 -= poll;
                sum1 += poll;
                cnt++;
            } else { // sum1 == sum2
                return cnt;
            }
        }

        return -1;
    }

	// 큐내부의 원소들의 합을 구하는 메서드
    public long getSum(Queue<Integer> queue) {
        long sum = 0;

        for (int node : queue) {
            sum += node;
        }

        return sum;
    }
}

소감

• 정확성 테스트 25,26,27번이 계속 통과가 안되었다. 뭐가 문제인지 계속 확인해보다가.. 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다. 라는 경고문이 있었고, 그걸 통해서 누적합을 int에서 long 타입으로 변경해주었더니 바로 통과했다.
• 처음에 규칙성 찾다가 별의 별 이상한 규칙성을 찾긴했는데...그걸로 구현하다가 틀렸다. 언제쯤 정확하게 바로 찾아낼 수 있으려나