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

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

프로그래머스

 

 

✔ 입출력 예시

두 큐 합 같게 만들기 입출력 예시

 

 

💡 포인트

      1️⃣ 언어에 따라 합 계산 과정 중 오버플로우 발생 가능성이 있으므로 long type 고려 필요

      2️⃣ queue1에서 뺀 원소는 무조건 queue2에 삽입해야하며, queue2에서 뺀 원소는 무조건 queue1에 삽입해야 함

            (제시된 원소 중 합의 결과에 포함되지 않는 원소는 ❌)

      3️⃣ 각 큐의 길이는 같지 않을 수 있음

 

 

❓ 풀이방법

     1️⃣ queue1과 queue2의 원소를 담을 큐 2개 선언

     2️⃣ 각 큐에 queue1과 queue2의 원소를 담으며 두 큐에 담긴 모든 원소들의 합과 각 큐 원소들의 합 구하기

     3️⃣ 각 큐 원소들의 합을 비교하여

           queue1에 담긴 원소의 합이 크다면 queue1에서 원소를 1개 빼고 이를 queue2에 담고 각 큐의 합에서도 이를 계산, 

           queue2에 담긴 원소의 합이 크다면 queue2에서 원소를 1개 빼고 이를 queue1에 담고 각 큐의 합에서도 이를 계산

     4️⃣ 각 큐 원소들의 합 모두가 두 큐에 담긴 모든 원소들의 합의 절반과 같을 때까지 3️⃣ 반복

            또는 각 원소들이 원래 자리를 찾기 전까지 반복

 

 

❗ 결과

   👉 테스트 통과

 

 

✔ 소스코드

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

public class Solution {  // 두 큐 합 같게 먼둘기

	public static void main(String[] args) {
//		int[] queue1 = {3, 2, 7, 2};
//		int[] queue2 = {4, 6, 5, 1};
		
//		int[] queue1 = {1, 2, 1, 2};
//		int[] queue2 = {1, 10, 1, 2};
		
		int[] queue1 = {1, 1};
		int[] queue2 = {1, 5};
		
//		int[] queue1 = {1, 1, 1, 1, 1};
//		int[] queue2 = {1, 1, 1, 9, 1};
		// result : 12

		System.out.println(solution(queue1, queue2));
	}

	private static int solution(int[] queue1, int[] queue2) {
		int result = 0;
		
		Queue<Integer> q1 = new LinkedList<>();
		Queue<Integer> q2 = new LinkedList<>();
		
		
		long sum = 0;  // 모든 큐의 합을 담을 변수
		long sum1 = 0;  // q1의 합을 담을 변수
		long sum2 = 0;  // q2의 합을 담을 변수
		
		for (int i = 0; i < queue2.length; i++) {
			q1.add(queue1[i]);
			sum += queue1[i];
			sum1 += queue1[i];			
			
			q2.add(queue2[i]);
			sum += queue2[i];
			sum2 += queue2[i];
		}
		
		long half = sum/2;  // 각 큐의 수의 합이 절반일 때의 수
		boolean same = true;  // 정해진 횟수 안에 각 큐의 합이 같을지 판별할 변수
		
		while(sum1 != half || sum2 != half) {
			if(result > queue1.length*3) {
				same = false;
				break;
			}
			
			if(!q1.isEmpty() && sum1 > sum2) { // sum1이 sum2보다 크다면
				int num = q1.poll();
				q2.add(num);
				sum1 -= num;
				sum2 += num;
			} else if(!q2.isEmpty() && sum1 < sum2){  // sum2가 sum1보다 크다면
				int num = q2.poll();
				q1.add(num);
				sum2 -= num;
				sum1 += num;	
			}
			result++; 
		}
		
		if(!same) {  // 제한 횟수 안에 두 큐의 합이 같지 않다면 result = -1
			result = -1;
		}
			
		return result;
	}

}