두 큐 합 같게 만들기

hyeongjun Jo·2022년 11월 26일
0

Programmers

목록 보기
3/7

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

문제

풀이

두 개의 큐의 합을 같게 만드는 평탄화 작업을 반복해야 하는 문제이다
큐의 모든 원소가 양수이므로 평탄화 작업을 반복할 수 있다.

먼저 두 큐의 합의 평균 sum = (sum1 + sum2) / 2을 구함

  • sum1(또는 sum2)sum과 같으면 두 큐의 평탄화 횟수를 출력
  • sum1sum보다 크면 queue1에서 빼고 queue2에 더함
  • sum2sum보다 크면 queue2에서 빼고 queue1에 더함

만약 sum이 홀수라면 -1을 출력한다

만약 반복횟수 r1, r2가 queue의 크기의 두 배보다 커진 것은
평탄화작업을 반복하다가 사이클이 완료된 횟수이므로 -1을 출력한다

코드

long sum1 = 0, sum2 = 0, sum;
        for (long num1 : queue1) {
            sum1 += num1;
            longQueue1.add(num1);
        }
        for (long num2 : queue2) {
            sum2 += num2;
            longQueue2.add(num2);
        }

입력받은 배열을 queue에 더하면서 합을 계산

int r1 = 0, r2 =0;

평탄화작업 반복횟수

전체코드

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

class Solution {

    public int solution(int[] queue1, int[] queue2) {
        Queue<Long> longQueue1 = new LinkedList<>();
        Queue<Long> longQueue2 = new LinkedList<>();
        long sum1 = 0, sum2 = 0, sum;
        for (long num1 : queue1) {
            sum1 += num1;
            longQueue1.add(num1);
        }
        for (long num2 : queue2) {
            sum2 += num2;
            longQueue2.add(num2);
        }
        sum = sum1 + sum2;
        if(sum%2==1) return -1;
        sum/=2;
        int limit = queue1.length*2;
        int r1 = 0, r2 =0;
        while (r1 <= limit && r2 <= limit) {
            if (sum1 == sum) return r1 + r2;
            if (sum1 > sum) {
                sum1 -= longQueue1.peek();
                sum2 += longQueue1.peek();
                longQueue2.add(longQueue1.poll());
                r1++;
            } else {
                sum2 -= longQueue2.peek();
                sum1 += longQueue2.peek();
                longQueue1.add(longQueue2.poll());
                r2++;
            }
        }
        return -1;
    }
}

느낀점

limit을 어떻게 선언할지에 대한 내용이 어려웠다.

profile
DevOps Engineer

0개의 댓글