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

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/118667

 

 

1차시도

public int solution(int[] queue1, int[] queue2) 
{
    long sum1 = queue1.Sum();
    long sum2 = queue2.Sum();

    if(sum1 == sum2) return 0; // 이미 같다면 수행 필요 없음

    long sum = sum1 + sum2;
    if(sum % 2 == 1) return -1; // 홀수는 같은 값으로 나눌 수 없음

    var q1 = new Queue<int>(queue1); 
    var q2 = new Queue<int>(queue2); 

    int maxTryCount = queue1.Length * 10;
    long target = sum / 2;
    int answer = 0;
    while(sum1 != target)
    {
        if(answer > maxTryCount) // 무한루프 방지
            return -1;

        if(sum1 < target)
        {
            int num = q2.Dequeue();
            q1.Enqueue(num);
            sum1 += num;
            ++answer;
        }
        else
        {
            int num = q1.Dequeue();
            q2.Enqueue(num);
            sum1 -= num;
            ++answer;
        }
    }
    return answer;
}

처음 지문을 읽었을 때, 하노이의 탑같이 순서가 뒤바뀔 수 있나 걱정했는데

큐가 두 개고 뺀 숫자는 반드시 다른 큐에 넣어야되니까 빙글빙글 순환하기만 함.

단, 처음에 주어질 때는 두 큐의 크기가 같지만, 최종 결과에서는 길이가 서로 달라도 되는 조건.  

 

 

지문에 친절히 long타입을 고려한 부분이 인상적이다.

그러나 sum을 long으로 처리했음에도 런타임 에러.

 

나의 풀이

public int solution(int[] queue1, int[] queue2) 
{
    var q1 = new Queue<long>(queue1.Select(s => (long)s)); 
    var q2 = new Queue<long>(queue2.Select(s => (long)s)); 

    long sum1 = q1.Sum();
    long sum2 = q2.Sum();

    if(sum1 == sum2) return 0; // 이미 같다면 수행 필요 없음

    long sum = sum1 + sum2;
    if(sum % 2 == 1) return -1; // 홀수는 같은 값으로 나눌 수 없음

    int maxTryCount = queue1.Length * 3;
    long target = sum / (long)2;
    int answer = 0;
    while(sum1 != target)
    {
        if(answer > maxTryCount) // 무한루프 방지
            return -1;

        if(sum1 < target)
        {
            long num = q2.Dequeue();
            q1.Enqueue(num);
            sum1 += num;
            ++answer;
        }
        else
        {
            long num = q1.Dequeue();
            q2.Enqueue(num);
            sum1 -= num;
            ++answer;
        }
    }
    return answer;
}

다 풀고 나서 실수 한 부분은 역시나 오버플로우.

 

1차 시도 때 첫 번째 줄의 long sum1 = queue1.Sum(); 는 int 형의 데이터 컨테이너를 만든 다음 값을 차례로 더한다. 그 후 long 타입에 암시적 캐스팅하면서 넣게 된다. 즉, 이미 Sum()이 실행된 시점에서 오버플로우가 발생한다.

 

Sum()은 대상이 되는 자료형에 맞춰서 리턴값이 결정되기 때문에 합계를 위해 넘겨주는 컬렉션이 long형으로 미리 캐스팅되어야 한다. 혹은 Sum()을 사용하지 말고 for문에서 하나씩 long으로 캐스팅해 가면서 더해도 된다.

 

[ 최대 시도 횟수 ]

maxTryCount는 최악의 경우 하나의 큐에서 한개만 빼고 다 옮기고, 다른 큐에서 옮겨진 것들 중 한 개 빼고 다시 전부 옮기는 경우가 있을테니, 3n을 넘지 않을 것.