링크

문제 링크

문제 설명

제한 사항

입출력 예 설명

풀이

1. 제한사항에서 큐들의 길이가 최대 30만 -> O(n)으로 해결 가능!
   1.1 근데 이 문제는 큐1 = [1, 1, 1, 8, 10, 9] 큐2 = [1, 1, 1, 1, 1, 1]같은 반례를 통해 O((q1사이즈 + q2사이즈) * 2)까지 커질 수 있더라.
   1.2 위 반례는 질문하기 코너에서.. 득템
2. sum 기준 작은 큐에서 큰 큐로 원소 떼주기 두 큐의 합의 같아질 때 까지 반복하면 끝!
3. 탈출조건은 매번 ++되는 answer가 (q1사이즈 + q2사이즈) * 2보다 커질때 -1 리턴하고 끝!

처음 문제를 보고나서 제일 먼저 들었던 생각..!

카카오 문제 진짜 오랜만이다 재밌닼ㅋㅋㅋ

핵심 알고리즘이라 할 수 있는 2번 로직을 떠올리긴했는데.. 진짜 이게 끝일까? 라는 의심을 계속 했다 ㅜㅜ

일단 다행인건 저 로직을 짜면서 의심을 한거라 문제는 생각보다 빨리 풀었다.

그리고 1.1을 생각해주지 않으면, 1번 테스트케이스를 통과하지 못한다.
(근데 나머진 다 맞길래 아.. 로직은 맞구나) 하고 품 ㅋㅋㅋ..

시작한진 얼마 안됐지만 직장을 가지고 취미삼아 푸는 알고리즘은 확실히 스트레스를 안받아서 좋다 ㅎ.ㅎ

코드

import java.util.*;
class Solution {
    public long getsum(int[] q) {
        long sum = 0;
        for(int i = 0; i < q.length; i++) 
        {
            sum += (long) q[i];
        }
        return sum;
    }
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        long sum1 = getsum(queue1);
        long sum2 = getsum(queue2);
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();        
        for(int i = 0; i < queue1.length; i++) {
            q1.add(queue1[i]);            
            q2.add(queue2[i]);
        }
        while(sum1 != sum2) {
            if(answer > (queue1.length + queue2.length) * 2)
                return -1;
            int val = 0;
            if(sum1 < sum2) {
                val = q2.poll();
                q1.add(val);
                sum1 += (long) val;
                sum2 -= (long) val;
            }
            else if(sum1 > sum2) {
                val = q1.poll();
                q2.add(val);
                sum1 -= (long) val;
                sum2 += (long) val;
            }
            else 
            {
                return answer;
            }
            answer++;
        }
        return answer;
    }
}