문제

문제 바로가기

풀이

첫 번째 풀이

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int middleIndex = queue1.length;
        // 1. queue1과 queue2를 이어서 새로운 queue를 만든다.
        int[] connectedQueue = new int[middleIndex*2];
        long targetSum = 0l;
        for(int i=0; i<middleIndex; i++) {
            connectedQueue[i]=queue1[i];
            connectedQueue[middleIndex+i]=queue2[i];
            targetSum += (queue1[i]+queue2[i]);
        }
        targetSum /= 2;
        
        // 2. queue에서 연속되는 원소의 합이 두 큐의 합의 절반이 되는 startIdx와 endIdx의 합을 구한다.
        int sumOfStartAndEndIdx = find(connectedQueue, targetSum);
        
        // (end - middleIdx) : queue1에 queue2의 end 인덱스까지를 넣는 작업 수
        // start : queue1에서 start 인덱스 앞까지를 제거하여 queue2에 넣는 작업 수
        // 총 작업 수 : (end - middleIdx) + start
        return sumOfStartAndEndIdx == -1? -1: sumOfStartAndEndIdx-(middleIndex-1);
    }
    
    public int find(int[] arr, long targetSum) {
        int s=0, e=0;
        long sum = arr[0];
        int min = Integer.MAX_VALUE;
        while(s<arr.length) {
            if(sum<targetSum) {
                if(e<arr.length-1) {
                    e++;    
                    sum+=arr[e];
                } else {
                    sum-=arr[s];
                    s++;       
                }
            } else if(sum>targetSum) {
                sum-=arr[s];
                s++;
            } else {
                if(e+s < min) {
                    min = e+s;
                }
                sum-=arr[s];
                s++;
            }
        }
        return min == Integer.MAX_VALUE ? -1: min;
    }
}

1. queue1과 queue2를 이은 새로운 큐를 만든다.
2. 큐에서 연속되는 원소의 합이 두 큐의 합의 절반이 되는 start값 + end값의 최솟값을 구한다.
3. 두 큐의 합을 같게 만들 수 있는 경우, (start + end의 최솟값) - (middleIdx-1) 값을 반환한다.
   • queue1에 queue2의 end 인덱스까지의 값을 모두 넣는다. (end - (middleIdx-1))번의 작업 소요)
   • 그런 다음 queue1에서 start 앞까지의 값을 모두 뺀다. (start번의 작업 소요)
   • 따라서 총 end - (middleIdx-1) + start 번의 작업 소요 ==> start+ end - (middleIdx-1)

그러나 위 코드는 계속해서 테케 9번, 14번을 통과하지 못 했다.
그 이유는 ! 위의 가정은 end가 queue2에 들어있을 때 의 케이스 만을 커버하기 때문이다.

정답 풀이

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int middleIndex = queue1.length;
        int[] connectedQueue = new int[middleIndex * 2];
        long targetSum = 0L;

        // queue1과 queue2를 연결하며 전체 합을 구함
        for (int i = 0; i < middleIndex; i++) {
            connectedQueue[i] = queue1[i];
            connectedQueue[middleIndex + i] = queue2[i];
            targetSum += (queue1[i] + queue2[i]);
        }

        // 합이 홀수면 나눌 수 없으므로 -1 반환
        if (targetSum % 2 != 0) return -1;
        
        targetSum /= 2;

        return find(connectedQueue, targetSum, middleIndex);
    }

    public int find(int[] arr, long targetSum, int middleIndex) {
        int s = arr.length - 1, e = arr.length - 1;
        long sum = arr[arr.length - 1];
        int minOperations = Integer.MAX_VALUE;
        int cur;

        while (e >= 0) {
            if (sum < targetSum) {
                // sum이 targetSum보다 작을 때, s 인덱스를 감소시켜 sum에 추가
                if (s > 0) {
                    sum += arr[--s];
                } else {
                    sum -= arr[e--];
                }
            } else if (sum > targetSum) {
                // sum이 targetSum보다 클 때, e 인덱스를 감소시켜 sum에서 제거
                sum -= arr[e--];
            } else {
                // targetSum과 같을 때, 작업 횟수를 계산하고 minOperations 갱신
                cur = 0;
                if (e >= middleIndex) {
                    cur = e - (middleIndex - 1) + s;
                } else if (e < middleIndex - 1) {
                    cur = e + 1 + middleIndex + s;
                } else {
                    cur += s;
                }

                minOperations = Math.min(minOperations, cur);
                sum -= arr[e--];
            }
        }

        return minOperations == Integer.MAX_VALUE ? -1 : minOperations;
    }
}

이것저것 시도하다가 .. 그냥 sum이 targetSum과 같을 때 모든 경우의 수를 분기해서 작업 수를 구하였고, 가장 적은 작업 수를 리턴하도록 구현했다.

1. if ( e >= middleIndex)
   • e가 queue2에 들어있는 경우
   • 작업의 수는 위에서 설명
2. else if ( e < middleIndex - 1)
   • e가 queue1에 들어있는데, 뒤에 다른 수가 있는 경우
   • e까지를 전부 queue2에 insert하고 (e+1번의 작업)
   • queue2에서 s 전까지의 수를 pop해야 한다. (middleIdx+s 번의 작업)
3. else
   • e가 queue1에 들어있는데, 뒤에 다른 수가 없는 경우
   • s 전까지의 수를 pop한다. (s번의 작업)

(슬라이딩 윈도우가 반대로 구현되어있는 것도 이것저것 시도하면서 바뀐 것... 정방향(왼->오)로 가도 상관없다.)

다른 풀이

다른 풀이들을 살펴보니 Queue를 사용하는 풀이가 많았다.

1. 실제 문제대로 queue1, queue2를 구성한다.
2. 각 queue 안 원소들의 합을 구한다.
3. while문을 돌면서 합이 큰 쪽에서 작은 쪽으로 원소를 하나씩 옮긴다.
4. while문은 두 합이 같아지거나, queue의 길이 * 4번 이상 돌게 된다면 빠져나온다.

• queue의 길이 * 4번 ? 두 큐에서 원소가 완전히 빠져나가 다시 똑같이 돌아오게 되는 경우의 작업의 수