[2022 KAKAO TECH INTERNSHIP] 두 큐 합 같게 만들기

[2022 KAKAO TECH INTERNSHIP] 두 큐 합 같게 만들기

🙋‍♂️ 들어가며

이번 문제는 총 2가지 풀이다.

queue

그리고

투포인터

먼저 queue로 풀때는 다음 조건들을 생각해야겠다.

1. q1, q2를 설정하고 합이 일치할때까지 구한다
2. (sum1, sum2) % 2 == 1 이면 -1 을 반환하고 종료

3. 단 짝수일때도 무한루프가 걸릴 수 있는걸 유념하고, 2번 조건만 보지는 말자. 이어서 최악의 케이스를 생각해보자

   3-1. (case-1) $q_1$에 $q_2$를 추가하고 전체 순회 -> 2n

   3-2. (case-2) $q_2$에 $q_1$을 추가하고 전체 순회 -> 2n

   즉 모든 경우를 합하여 4n이 최악의 실행연산이므로, 4n을 넘어가는 연산은 없겠다

4. sum1 과 sum2가 같지 않을때까지만 계속 계산을 수행하자, 3번조건을 limit으로 설정하여 말이다

✅ 코드 : queue

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

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int cnt = 0;
        
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        long sum1 = 0;
        long sum2 = 0;
        
        int N = queue1.length;
        for (int i = 0; i < N; i++) {
            q1.add(queue1[i]);
            sum1 += queue1[i];
            
            q2.add(queue2[i]);
            sum2 += queue2[i];
        }
        
        // 1. 조기종료
        if ( (sum1 + sum2) % 2 == 1) return -1; 
        
        
        // 2. 수행
        int limit = (queue1.length + queue2.length) * 2;
        while (sum1 != sum2) {
            
            // limit
            if (cnt > limit) return -1;
            
            if (sum1 > sum2) {
                int cur_val = q1.poll();
                sum1 -= cur_val;
                q2.add(cur_val);
                sum2 += cur_val;
            }
            else if (sum1 < sum2) {
                int cur_val = q2.poll();
                sum2 -= cur_val;
                q1.add(cur_val);
                sum1 += cur_val;
            }
            
            // 횟수 추가
            cnt++;
        }
        
        
        return cnt;
    }
}