[Level 2] 두 큐 합 같게 만들기

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

프로그래머스

슬라이딩 윈도우 문제 같긴 하다

 

근데 편하게 인덱스 조절 간단하게 하는 queue1에서 빠지는 거  queue2에 실제로 붙이면서 해볼까?

근데

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000

이 제한 사항 때문에 메모리를 너무 쓸 수도 있겠구나

 

그럼 arrayList에 queue1과 queue2를 담아 remove(0) 하고 addLast() 해주자

했는 데 시간 초과 걸림

 

아직 while문 종료 조건을 완전히 이해 못 했지만 remove(0) 함수를 안 쓰고 풀기 위해 인덱스 조절을 하자

이런 식으로 구성하고 빨간색 S E가 합이 충족되면 종료하자

 

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;

        ArrayList<Integer> arrayList = new ArrayList<>();

        long queue1_sum = 0;
        long queue2_sum = 0;
        long goal;

        int queue1_start_index = 0;
        int queue1_end_index = queue1.length-1;
        int queue2_start_index = queue1.length;
        int queue2_end_index = queue1.length+ queue2.length -1;

        for(int value: queue1) {
            queue1_sum += value;
            arrayList.add(value);
        }
        for(int value: queue2) {
            queue2_sum += value;
            arrayList.add(value);
        }

        goal = (queue1_sum+queue2_sum)/2;

        while(true){
            if(queue1_sum > goal){
                int tmp = arrayList.get(queue1_start_index);
                queue1_start_index = (queue1_start_index+1)%(arrayList.size());
                queue2_end_index = (queue2_end_index+1)%(arrayList.size());
                queue1_sum -= tmp;
                queue2_sum += tmp;
            }
            else if(queue1_sum < goal){
                int tmp = arrayList.get(queue2_start_index);
                queue1_end_index = (queue1_end_index+1)%(arrayList.size());
                queue2_start_index = (queue2_start_index+1)%(arrayList.size());
                queue1_sum += tmp;
                queue2_sum -= tmp;
            }
            else{
                return answer;
            }
            answer++;

            if( answer> queue1.length*3)
                return -1;
        }
    }
}

근데 -1을 꺼내는 종료 조건이 도대체 뭐지

ex) [1,1,1,8,10,9] [1,1,1,1,1,1]

[1,1,1,8,10,9] [1,1,1,1,1,1] [1,1,1,8,10,9] 사실은 이런 모습이 되면 끝이니까 queue1.length *3 인 건가 아직도 모르겠다