Programmers_두 큐 합 같게 만들기

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

---

문제 파악

길이가 같은 두 큐가 주어지는데 하나의 큐를 골라 추출하고 그 요소를 다른 큐에 집어 넣는 과정을 반복하여 두 큐의 합이 같아지게 하면 된다.

접근 방법

두 큐의 합을 같게 만들어야 하기 때문에 deque를 통해 queue를 만들고 이를 통해서 맨 앞의 요소들을 뽑아내고 옮겨서 이를 조건에 따라 반복하며 처리한다.

코드 구현

from collections import deque

def solution(queue1, queue2):
    # 주어진 큐를 deque를 통해 q1, q2 생성
    q1 = deque(queue1)
    q2 = deque(queue2)

    # 각 큐의 합을 미리 계산
    sum1 = sum(q1)
    sum2 = sum(q2)

    # 목표는 두 큐의 합이 같아지는 것
    target = (sum1 + sum2) // 2

    # 큐의 총 길이
    q_size = len(q1)

    # q1과 q2에서 원소를 옮기는 과정의 최대 횟수는 (큐 길이) * 3
    for i in range(0, 3 * q_size):
        # q1의 합이 target과 같다면 이를 리턴한다.
        if sum1 == target:
            return i

        # 만약 q1의 합이 target보다 작으면 q2에서 요소를 가져와서 더한다.
        elif sum1 < target:
            temp = q2.popleft()
            q1.append(temp)
            sum1 += temp
            sum2 -= temp

        # 만약 q1의 합이 target보다 크면 q1에서 요소를 가져와서 q2로 더한다.
        else:
            temp = q1.popleft()
            q2.append(temp)
            sum1 -= temp
            sum2 += temp

    # 반복문을 다 돌렸을 때 안 되면 -1을 리턴
    return -1

배우게 된 점

• 1차 코드

  from collections import deque
  
  def solution(queue1, queue2):
      # 주어진 큐를 deque를 통해 q1, q2 생성
      q1 = deque(queue1)
      q2 = deque(queue2)
  
      q_size = len(q1)
  
      # 큐의 합을 같게 만들기 위해 평균을 구함
      avg = sum(q1) + sum(q2) / 2
  
      # 질문 1. 왜 3 * q_size까지 반복문을 진행하는지!?
      for i in range(0, 3 * q_size):
          # q1의 합이 평균과 같다면 이를 리턴한다.
          if sum(q1) == avg:
              return i
          
          # 만약 q1의 합이 평균보다 작으면 q2에서 요소를 가져와서 더한다.
          elif sum(q1) < avg:
              temp = q2.popleft()
              q1.append(temp)
          
          # 만약 q2의 합이 평균보다 작으면 q1에서 요소를 가져와서 더한다.
          else:
              temp = q1.popleft()
              q2.append(temp)
      
      # 반복문을 다 돌렸을 때 안 되면 -1을 리턴
      return -1
  

1차 코드를 통해 제출을 하면 시간 초과가 나온다 ㅠ 이유가 뭘까….

• 2차 코드

  from collections import deque
  
  def solution(queue1, queue2):
      # 주어진 큐를 deque를 통해 q1, q2 생성
      q1 = deque(queue1)
      q2 = deque(queue2)
  
      # 각 큐의 합을 미리 계산
      sum1 = sum(q1)
      sum2 = sum(q2)
  
      # 목표는 두 큐의 합이 같아지는 것
      target = (sum1 + sum2) // 2
  
      # 큐의 총 길이
      q_size = len(q1)
  
      # q1과 q2에서 원소를 옮기는 과정의 최대 횟수는 (큐 길이) * 3
      for i in range(0, 3 * q_size):
          # q1의 합이 target과 같다면 이를 리턴한다.
          if sum1 == target:
              return i
  
          # 만약 q1의 합이 target보다 작으면 q2에서 요소를 가져와서 더한다.
          elif sum1 < target:
              temp = q2.popleft()
              q1.append(temp)
              sum1 += temp
              sum2 -= temp
  
          # 만약 q1의 합이 target보다 크면 q1에서 요소를 가져와서 q2로 더한다.
          else:
              temp = q1.popleft()
              q2.append(temp)
              sum1 -= temp
              sum2 += temp
  
      # 반복문을 다 돌렸을 때 안 되면 -1을 리턴
      return -1
  

sum 함수를 사용하는 것보다 sum 값을 변수로 선언해서 더하고 빼주는게 시간 대비 효율이 좋을 것 같다!