99클럽 코테 스터디 8일차 TIL + 두 큐 합 같게 만들기 (java)

 

💡 문제

• 두 큐 합 같게 만들기
• https://school.programmers.co.kr/learn/courses/30/lessons/118667

권장 시간

• 1시간

소요 시간

• 1시간 45분 + a

풀이 코드

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        
        long sum = 0;
        long[] mergedQueue = new long[queue1.length * 2];
        for (int i = 0; i < queue1.length; i++) {
            // 두 큐 합치기
            mergedQueue[i] = queue1[i];
            mergedQueue[queue1.length + i] = queue2[i];
        }
        
        // 투 포인터 설정
        int l1 = 0;
        int r1 = queue1.length - 1;
        
        int l2 = queue1.length;
        int r2 = queue1.length * 2 - 1;

        // 각 큐의 합 구하기
        long sumOfQ1 = sumOfQ(queue1);
        long sumOfQ2 = sumOfQ(queue2);
        
        // 목표값 구하기
        long target = (sumOfQ1 + sumOfQ2) / 2;
        
        // 모든 원소의 합이 홀수인 경우 종료  
        if ((sumOfQ1 + sumOfQ2) % 2 != 0) {
            return -1;
        }
        
        while (answer < 4 * queue1.length) {
            // queue1 합이 더 작은 경우
            if (sumOfQ1 < sumOfQ2) {
                // queue2에서 pop, insert 하기
                l2 = (l2 + 1) % mergedQueue.length;
                r1 = (r1 + 1) % mergedQueue.length;
                sumOfQ1 += mergedQueue[r1];
                sumOfQ2 -= mergedQueue[r1];
                
                answer++;
            }
            // queue2 합이 더 작은 경우
            else if (sumOfQ1 > sumOfQ2) {
                // queue1에서 pop, insert 하기
                l1 = (l1 + 1) % mergedQueue.length;
                r2 = (r2 + 1) % mergedQueue.length;
                sumOfQ1 -= mergedQueue[r2];
                sumOfQ2 += mergedQueue[r2];
                
                answer++;
            }
            
            // 합이 같아지면 종료
            if (sumOfQ1 == target && sumOfQ2 == target) {
                break;
            }
        }
        
        return sumOfQ1 == sumOfQ2 ? answer : -1;
    }
    
    private long sumOfQ(int[] queue) {
        return Arrays.stream(queue).sum();
    }
}

주요사항

long 타입으로 값 받는거랑, 두 배열 값의 총합을 for문에서 돌리지 않고 따로 빼서 구해야 시간 초과가 나지 않는다.

그리고, 모든 원소의 값이 홀수인 경우 애초에 각 배열의 합이 같아질 수 없으니 -1을 return 하는 것도 중요한 예외였다.

왜 곱하기 4를 했을까?

while (answer < 4 * queue1.length)

큐의 원소를 이동시키는 최악의 경우를 고려했다. (각 큐로 2번씩 이동되는 경우)

1. 큐1의 모든 원소를 큐2로 이동 (큐1의 길이 만큼 이동).
2. 큐2의 모든 원소를 큐1로 이동 (큐2의 길이 만큼 이동).
3. 다시 큐1의 모든 원소를 큐2로 이동 (큐1의 길이 만큼 이동).
4. 다시 큐2의 모든 원소를 큐1로 이동 (큐2의 길이 만큼 이동).

이렇게 하면 총 4번의 전체 큐 길이만큼의 이동이 이루어지게 된다.

→ 따라서 최악의 경우 각 큐의 길이의 4배 만큼의 이동이 필요할 수 있다.

 

이 제한사항을 넘어도 두 큐의 합이 같아지지 않으면, 더 이상 합을 맞출 수 없으므로 -1을 반환한다.

투 포인터 알고리즘

[코딩테스트/프로그래머스]두 큐 합 같게 만들기(Java)

[코딩테스트/프로그래머스]두 큐 합 같게 만들기(Java)

풀이 방법이 도저히 떠오르지 않아서 이 글을 참고했다.

투 포인터 알고리즘 아주 예전에 배운 것 같은데, 이렇게 제대로 써본건 처음이었다.

왜 괜히 큐가 아니라 배열로 문제가 주어졌는지 알 것 같다.

문제의 의도를 잘 파악하는 것도 중요한 것 같다.