[프로그래머스] Lv.2 두 큐 합 같게 만들기 (Java)

문제

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

프로그래머스

---

풀이

첫 번째 풀이 : 실패

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int middleIndex = queue1.length;
        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;
        
        int sumOfStartAndEndIdx = find(connectedQueue, targetSum);
        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;
    }
}

 

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

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

end가 queue1에 들어있는 경우도 커버해주어야 한다.

 

정답 풀이 

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과 같을 때 모든 경우의 수를 분기해서 작업 수를 구하였고, 가장 적은 작업 수를 리턴하도록 구현했다.

 

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

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

 

다른 풀이

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

1. 실제 문제대로 queue1, queue2를 구성한다.
2. 각 queue 안 원소들의 합을 구한다.
3. while문을 돌면서 합이 큰 쪽에서 작은 쪽으로 원소를 하나씩 옮긴다.
4. while문은 두 합이 같아지거나, `queue의 길이 * 4번` 이상 돌게 된다면 빠져나온다.
- queue의 길이 * 4번 ? 두 큐에서 원소가 완전히 빠져나가 다시 똑같이 돌아오게 되는 경우의 작업의 수

 

 

실행 시간은 나처럼 슬라이딩 윈도우를 사용하는 것이 더 빠르다.

그렇지만 실제 코테 상황에서는 모든 경우의 수를 분기하는 데에 시간이 더 오래 걸릴 수 있어서 Queue를 사용해서 간단히 풀이하는 것이 더 나을 것 같기도 하다.