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

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

 

 

이번 문제는 제한사항에 long type 고려가 필요하다고 주의사항이 명시되어 있는 문제였다.

문제의 풀이 방식을 생각해내고 예외를 구상하는 과정까지는 간단했지만 long 타입으로의 타입 캐스팅을 잘 하지 않으면 후반부 테스트 케이스에서 컴파일 에러가 나니 주의해야하는 문제였다.

 

 

먼저 문제의 풀이 방향성은

양 큐의 값이 "얼마" 정도의 차이(diff)가 있는지 확인하고, 해당 차이를 각 queue에서 뺴고 더함을 얼마만큼 해서 매꿀수 있는지를 queue의 dequeue로 체크를 하는방식.

 

양쪽의 숫자를 계속 빼서 차이값을 조정해가면 0으로 만드는 방식으로, while 문을 사용하되 아래의 예외사항 2가지를 주의해서 풀었다.

 

1. 두 수의 합의 홀수 이거나

2. 쪼갤 수 없는 값이 존재하거나

        a) 두 개수의 합 x2 만큼의 pop을 진행하여도 while문이 끝나지 않는 경우

        b) 혹은 차이가 너무커서 한쪽의 값을 계속 빼서 어느 한쪽의 queue 개수가 0개가 되버린 경우

 

의 2가지 케이스를 예외처리를 진행하여 while(diff != 0 ) 으로 문제를 풀었다.

 

 

 

---

 

 

 

 

public long solution(int[] queue1, int[] queue2)
{
    Queue<int> q1 = new Queue<int>(queue1);
    Queue<int> q2 = new Queue<int>(queue2);
    long answer = 0;
    long diff = 0; // queue1가 더 큰만큼 +, 작으면 - 로 표시. diff 가 0이면 둘의 합이 같아지는 순간.
    long sum1 = queue1.Select(x => (long)x).Sum();
    long sum2 = queue2.Select(x => (long)x).Sum();

    diff = (sum1 - sum2); // 두 큐의 합이 같아지는 순간을 찾기 위해서.

    // 두 수의 합의 홀수는 불가능한 경우.
    if((sum1 + sum2) % 2 != 0) return -1;

    while (diff != 0)
    {
        if(diff > 0) // queue1이 더 크면 queue1에서 하나 꺼내서 queue2에 넣음.
        {
            answer++; // 큐를 옮길 때마다 카운트 증가.
            if(q1.Count == 0) return -1; // queue1이 비어있으면 불가능한 경우.
            int num = q1.Dequeue();
            q2.Enqueue(num);
            diff -= (long)num * 2; // queue1에서 꺼낸 수를 두 번 빼줌.
        }
        else // queue2가 더 크면 queue2에서 하나 꺼내서 queue1에 넣음.
        {
            answer++; // 큐를 옮길 때마다 카운트 증가.
            if(q2.Count == 0) return -1; // queue2가 비어있으면 불가능한 경우.
            int num = q2.Dequeue();
            q1.Enqueue(num);
            diff += (long)num * 2; // queue2에서 꺼낸 수를 두 번 더해줌.
        }

        if(answer > (queue1.Length + queue2.Length) *2) return -1;
    }
    return answer;
}