C# [프로그래머스] Lv.2 두 큐 합 같게 만들기

 

 

 

 

 

 

 

 

 

 

문제 설명

 

 

 

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

 

문제에서 넘겨주는 queue는 배열로 이루어져 있지만 제일 앞에 있는 배열 원소가 첫번째로 빠져나와야 하는 queue의 원소로 가정해서 풀어야 한다.

 

위와 같이 두개의 큐를 넘겨주고 모든 큐의 합을 더한 뒤 2로 나눈 값이 각각의 큐의 합이 되도록 만들어야 한다.

 

즉 위의 queue1 의 총 합은 14이고 queue2의 총 합은 16이다. 둘을 합하면 30이고 각 큐의 원소의 합이 15가 되게 만들어야 하기 때문에 queue1의 원소와 queue2 원소를 Enqueue하고 Dequeue 해가며 작업한다.

 

이때 return값은 제일 적은 경우로 작업한 횟수를 넘겨주면 되고 불가능 할 경우 -1을 return하면 된다.

 

 

 

풀이 과정

 

제한사항

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
• 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

 

위 제한사항을 보면 딱 봐도 어마어마한 연산이 예상되고 필요하지 않은 계산은 사전에 제외시키는 작업이 필요하다고 생각했다. 

 

우선 각 원소의 합을 모두 더한 값이 홀수일 경우에는 무슨 짓을 해도 각 큐의 합이 2로 나눈값으로 절대 같아질 수 없다.

 

이런 상황을 미리 return -1 시켜버리면 불필요한 계산은 어느정도 걸러낼 수 있겠다고 생각했다.

(물론 예시의 모든 합을 짝수로 제공했을 수도 있음)

 

 

각 배열의 합을 구한 뒤 배열은 횟수를 연산할 queue로 바꿔주고 각각의 연산 횟수를 count 한다.

 

반복문을 돌려야 하기에 maxCount도 선언해주고 양쪽 queue의 길이가 같다는 제한사항이 있었기 때문에 최대 3번 왔다갔다 할 경우 정도로 안전하게 maxCount를 선언해준다.

 

이후 조건문을 돌려 1번 배열의 합이 2번 배열보다 컸을 경우에는 1번 배열에서 먼저 dequeue 해서 2번 배열에 넣어주고

 

2번 배열의 합의 1번 배열의 합보다 컸을 경우에는 2번 배열에서 dequeue 해서 1번 배열로 넣어준다.

 

각각의 이동마다 count++ 해주면 최종적인 횟수를 return 한다.

 

 

 

해당 코드

 

 

using System;
using System.Collections.Generic;

public class Solution 
{
    public int solution(int[] queue1, int[] queue2) 
    {
        // 각 큐의 합을 계산
        long sum1 = 0;
        long sum2 = 0;
        for (int i = 0; i < queue1.Length; i++) 
        {
            sum1 += queue1[i];
            sum2 += queue2[i];
        }
        
        long totalSum = sum1 + sum2;
        
        // 전체 합이 홀수이면 두 큐의 합을 같게 만들 수 없음
        if (totalSum % 2 != 0) 
        {
            return -1;
        }
        
        long target = totalSum / 2;
        
        // 큐로 변환
        Queue<int> q1 = new Queue<int>(queue1);
        Queue<int> q2 = new Queue<int>(queue2);
        
        int maxCount = queue1.Length * 3;
        
        int count = 0;
        
        while (count <= maxCount) 
        {
            if (sum1 == target) // sum1이 target과 같아지면 필요한 이동 횟수(count)를 반환
            {
                return count;
            }
            else if (sum1 > target)   // sum1이 target보다 크다면 q1에서 원소를 빼서 q2로 옮김
            {
                // 큐1에서 Enqueue하여 큐2로 이동
                int dequeueNum = q1.Dequeue();
                sum1 -= dequeueNum;
                q2.Enqueue(dequeueNum);
            } 
            else   // sum1이 target보다 작다면 q2에서 원소를 빼서 q1으로 옮김
            {
                // 큐2에서 Dequeue하여 큐1으로 이동
                int dequeueNum = q2.Dequeue();
                sum2 -= dequeueNum;
                sum1 += dequeueNum;
                q1.Enqueue(dequeueNum);
            }
            count++;
        }
        
        return -1; // 가능한 방법이 없을 경우
    }
}