[프로그래머스] - 두 큐 합 같게 만들기

JIWOO YUN·2023년 4월 18일
0

문제링크

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

구현방법

각 전체의 합을 구하고 /2 진행 -> 두큐가 가져야하는 값

각 큐의 값들을 계산해두고 만약 들어가는 값이 두 큐가 가져야하는 값보다 클 경우 -1 리턴해준다.

각 큐의 합을 계속 갱신하면서 두 큐가 가져야하는 값보다 큰 값일 경우 queue에서 빼서 다른 큐에 넘겨주고 각 큐값의 합을 가지고 있는 값을 갱신

두 큐가 가져야하는 값을 둘다 가지게 되면 종료

-- 처음에 간과했던점--

최대 회전수 ==> 원래큐가 다 돌고 원래대로 돌아가는 횟수 ==> queue1 * 4 번이 최대 횟수

구현알고리즘

Queue

CODE

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


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

        long all_sum = 0;

        long max = queue1.length*4;
        for(int idx= 0; idx <queue1.length;idx++)
        {
            all_sum += queue1[idx];
            all_sum += queue2[idx];
        }
        all_sum /=2;


        //각 큐의 값 갱신용
        long queue1_sum = 0;
        long queue2_sum = 0;

        Queue<Integer> Q1 = new LinkedList<>();
        Queue<Integer> Q2 = new LinkedList<>();

        for(int idx= 0; idx <queue1.length;idx++)
        {
            //가장 큰값이 현재 둘이 가져야하는 값보다 크면 -1 리턴
            if(all_sum < queue1[idx] || all_sum < queue2[idx])
                return -1;
            queue1_sum += queue1[idx];
            Q1.offer(queue1[idx]);

            queue2_sum += queue2[idx];
            Q2.offer(queue2[idx]);
        }

        //둘이 같아야 되는 값이 다를 경우에는 계속 반복
        while(queue1_sum != all_sum && queue2_sum != all_sum){
            if(queue1_sum > all_sum){
                int num = Q1.poll();
                queue1_sum-= num;

                Q2.offer(num);
                queue2_sum+=num;

                answer+=1;
                continue;
            }

            if(queue2_sum > all_sum){
                int num = Q2.poll();
                queue2_sum-= num;

                Q1.offer(num);
                queue1_sum+=num;
                answer+=1;
            }

            //최대 횟수를 넘기면 out
            if(answer > max)
                return -1;
        }
        return answer;
    }
}
profile
Backend Developer 지원 / 도전

0개의 댓글