두 큐 합 같게 만들기

• 문제 : 두 큐 합 같게 만들기
  • 간단 요약
    • 규칙
  • 데이터
  • 해결책
    • 트러블 슈팅
      • 의문점
    • 뒤에 다른 원소가 없을 때
    • 뒤에 다른 원소가 있을 때
      • 결론
    • 전체 코드

문제 : 두 큐 합 같게 만들기

• 간단 요약

  두 큐에 원소가 주어졌을 때, Queue 연산을 이용해서 양쪽의 Queue 원소 합을 동일하게 해보자

  • 규칙

    1. pop + insert 한번이 한번의 작업
    2. 절대로 균형을 맞출 수 없는 경우는 -1 출력

• 데이터

  	queue1	queue2	각 원소의 크기
  의미	Queue1	Queue2	Queue에 들어갈 각각의 데이터
  범위	1 ~ 300,000	1 ~ 300,000	1 ~ 10^9

• 해결책

  양쪽 Queue의 합을 관리하는 변수 하나와, 양쪽에서 참조 및 삽입, 삭제가 가능한 덱을 쓰자

  각 원소의 크기가 매우 크므로 합 관련은 long long을 써서 OverFlow를 방지해야 한다.

  • 트러블 슈팅

    이 문제에서 중요한 것은 어떤 방법을 쓰더라도 Queue의 원소 합을 같게 만들 수 없는 경우를 찾는 것이다.

    처음에는 언젠가 Cycle이 돌 것이라고 생각했고, 초기 Queue를 복사한 Copy를 하나 두어서, 누적합이 초기와 같아지고 사이즈도 같을 때,
    배열을 돌면서 원소가 전부 같은지를 탐지하여 구별하는 로직을 작성했지만 11번 Case에서 Time Limit이 나왔다.

    찾아본 결과 사이즈의 배수를 곱하는 것이 해결책이라고 적혀는 있었지만 제대로 된 이유가 없었던 것 같아 고민하다가 찾아냈다.

    결론적으로 최악의 경우는 한쪽 Queue의 맨 뒤에서 한 개 앞의 원소 혼자 있어야지 양쪽 Queue의 합이 동일해지는 경우다.

    예를 들어

    	Queue1	Queue2
    데이터	[1,1,1,1]	[1,1,7,1]
    사이즈	4	4
    합	4	10

    위와 같이 입력이 들어왔다고 가정해보자

    초기 Queue의 사이즈를 N이라고 둘 때,

    본 Case에서 N==4이다.
    최악의 경우를 따지는 것이므로 구체적인 로직은 생각하지 않는다.

    7이 혼자 있기 위해서는 7까지를 넘겨야 하므로 Queue2의 N-1개의 원소를 Queue1에 넘겨야 한다.

    그러면 아래와 같이 될 것이다

    	Queue1	Queue2
    데이터	[1,1,1,1,1,1,7]	[1]
    사이즈	7	1
    합	13	1

    이때 N-1개만큼 넘긴 것이므로 누적 작업 횟수는 N-1이 된다

    본 Case에서 현재 누적 작업 횟수는 4-1 => 3이 된다.

    그리고 Queue1의 현재 크기는 2N-1이 되었고,
    여기서 마지막 7을 제외한 2N-2개의 원소를 Queue2로 옮긴다.

    그러면

    	Queue1	Queue2
    데이터	[7]	[1,1,1,1,1,1,1,]
    사이즈	1	7
    합	7	7

    위와 같이 되며 균형이 맞춰진다.

    이 때 2N-2만큼 넘겼으므로 총 누적 작업 횟수는 3N-3이 된다.

    본 Case에서 총 누적 작업 횟수는 3+6 => 9가 된다.

    • 의문점

      그러면 본 경우에서 7이 혼자 남겨지는 경우는 이해가 됐겠지만, 왜 한쪽 Queue의 맨 뒤에서 한 개 앞의 원소 혼자 남는 것이 최악의 경우인지에 대해서 의문이 남았을 것이다.

      왜냐하면 이 문제에서 작업 횟수가 많아지는 경우는 군형을 맞췄을 때,
      맨 뒤에 있는 원소가 자신이 원래 존재하던 Queue를 기준으로, 뒤에는 다른 원소가 존재해야 하기 때문이다.

      경우의 수를 나눠서 뒤에 다른 원소가 있었을 때, 없었을 때로 설명하겠다.

      • 뒤에 다른 원소가 없을 때

        이 경우는 간단하다 맨 뒤의 원소가 남는 것인 경우인데,
        Queue의 특성상 그냥 앞의 것에서 필요한만큼만 이동시키면 되기 때문에, N-1만큼만 이동 시키면 된다.

      • 뒤에 다른 원소가 있을 때

        만약 다른 원소가 있다면, Queue의 특성상 뒤의 원소와 이격시키기 위해서는 자기 자신까지 옆 Queue로 이동시켜야 한다.

        만약 자신의 위치가 Queue로부터 X번째였다면, X만큼 작업하게 될 것이다.

        그리고 자기 자신은 남아야 하므로 이동한 곳에서 자신 하나를 빼고 나머지 전부를 이동시켜야 한다.

        그렇다면 원래 Queue에는 N만큼 있었을 것이고, 여기서 X만큼 들어와 N+X만큼 있던 상태에서,
        N+X-1만큼 추가적으로 작업을 해야 하는 것이다.

        그래서 최종적으로 N+2X-1만큼의 작업이 필요해지게 되는데, X가 N인 경우는 뒤에 다른 원소가 없어서 성립하지 않으므로,
        N-1일 경우가 최악의 경우이며 이 때 총 3N-3만큼의 작업이 필요해지게 된다.

        그럼 Queue 내의 여러 개가 묶였을 경우에 대해서도 의문이 있겠지만,
        결론적으로 앞에 것과 묶일 수록 오히려 옆쪽의 Queue로 갔다가 다시 돌아오는 작업량만 줄어들어 작업 횟수는 줄어들게 된다.

    • 결론

      맨 뒤에서 앞에 하나만 남는 것이 균형을 맞출 수 있을 때 최악의 경우가 된다

  • 전체 코드

      // file: "solution.cpp"
      #include <string>
      #include <vector>
      #include <queue>
      #include <deque>
    
      using namespace std;
    
      long long totalSum = 0;
      long long currentQueue1TotalSum = 0;
      long long currentQueue2TotalSum = 0;
      long long halfSum = 0;
    
      deque<int> que1;
      deque<int> que2;
    
      int solution(vector<int> queue1, vector<int> queue2) {
                
          for(int i = 0; i < queue1.size(); i++){
              // 모든 queue 원소의 합 계산
              totalSum += (queue1[i] + queue2[i]);
                    
              // queue1 원소의 합 계산
              currentQueue1TotalSum += queue1[i];
              // queue2 원소의 합 계산
              currentQueue2TotalSum += queue2[i];
                    
              // 덱으로 이동
              que1.push_back(queue1[i]);
              que2.push_back(queue2[i]);
          }
                
          // 원래 사이즈 저장
          int size = que1.size();
                
                
          // 각 큐의 합이 동일해질 때의 합 크기 
          // 양쪽이 평등해진다는건 주어진 원소들의 총 합을 절반씩 나눠가진다는 것
          halfSum = totalSum / 2;
                
          // 작업 횟수
          int workCnt = 0;
                
          // 만약 현재 한쪽 queue 원소의 총 합이 halfSum과 같아진다면 양쪽이 평등해진 것이므로 탈출, 아니면 반복
          while(currentQueue1TotalSum != halfSum){
              // 특수한 케이스지만 여기서 생각해볼 수 있는 최악의 경우의 수는 
              // 한쪽 queue의 맨 뒤에서 한 개 앞의 원소가 혼자 있어야 평등해지는 경우의 수
              // ex [1,1,1,1], [1,1,7,1]의 경우
              // 9번의 이동을 통해 [7], [1,1,1,1,1,1,1]가 됨
              // => 다시 정리하면 최악의 경우는
              // 오른쪽에서 혼자 있어야 하는 n-2번째 원소까지 왼쪽으로 옮긴 다음 (이렇게 되면 n-1만큼 이동, 왼쪽 Queue의 사이즈는 n + n-1 => 2n -1, 오른쪽은 1)
              // 왼쪽의 마지막 하나를 제외한 나머지를 전부 이동 (이렇게 되면 2n - 2(현재 왼쪽에는 2n-1만큼 있었으므로) 만큼 이동, 왼쪽 Queue 사이즈는 1, 오른쪽은 2n-1)
              // 그렇게 되면 총 3n-3만큼을 이동해서야 나오게 됨
              // 맨 뒤에 무언가가 존재해야 위와 같은 경우가 나오기 때문에, 맨 뒤에 것만 정답일 경우는 그냥 앞에 원소들만 이동 시키면 되므로 성립하지 않고,
              // 다른 앞에 것이 같이 포함되거나 더 앞의 것만 혼자 있어야 할 경우 오히려 덜 이동하게 되므로 맨 뒤에서 한 개 앞의 것이 혼자 남아있어야 할 때가 가장 최악의 경우
              // 결론적으로 대략 3n의 연산이 넘어갔는데도 균형을 맞추지 못한 경우는 절대로 평행하게 맞출 수 없는 경우의 수임을 알 수 있다.
              if(workCnt >= size*3){
                  return -1;
              }else{
                  // 아니면 둘 중 큰 쪽의 것을 떼어서 작은 쪽으로 이동시킴
                  if(currentQueue1TotalSum > currentQueue2TotalSum){
                      currentQueue1TotalSum -= que1.front();
                      currentQueue2TotalSum += que1.front();
                      que2.push_back(que1.front());
                      que1.pop_front();
                  }else{
                      currentQueue1TotalSum += que2.front();
                      currentQueue2TotalSum -= que2.front();
                      que1.push_back(que2.front());
                      que2.pop_front();
                  }
                  workCnt++;
              }
          }
          return workCnt;
      }