[프로그래머스/Swift] 118667번 - 두 큐 합 같게 만들기

🔗 문제 링크

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

💡 구현 아이디어

1. 각 원소의 합으로 평균을 구함 → 합이 홀수면 평균은 소수점 단위이므로 -1 반환
2. 두 큐의 합을 같게 맞춤 → 그리디 방식으로 둘중 큰 큐에서 작은 큐로 이동
3. 두 큐가 같으면 횟수를 반환, 최대 이동 횟수를 넘어가면 -1 반환

💻 코드

import Foundation

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
  var q1: [Int] = []
  var q2: [Int] = []
  var q1Sum: Int = 0, q2Sum: Int = 0
  var q1Max: Int = -1, q2Max: Int = -1
  var q1Idx: Int = 0, q2Idx: Int = 0
  var result: Int = 0
  let MAX_RESULT: Int = (queue1.count + queue2.count) * 2
  // 초기값 설정
  for idx in 0..<queue1.count {
    q1.append(queue1[idx])
    q1Sum += queue1[idx]
    q2.append(queue2[idx])
    q2Sum += queue2[idx]
    q1Max = max(q1Max, queue1[idx])
    q2Max = max(q2Max, queue2[idx])
  }
  // 합이 홀수면 못구하므로 -1 반환
  if (q1Sum + q2Sum) % 2 == 1 {
    return -1
  }
  // 큐의 요소 이동
  while q1Sum != q2Sum {
    // 최대 이동 횟수를 넘어가면 -1 반환
    if result > MAX_RESULT {
       return -1
    }
    // 합이 큰 큐에서 하나를 빼서 다른 한쪽에 넣음
    if q1Sum > q2Sum {
      let num = q1[q1Idx]
      q1Idx += 1
      q1Sum -= num
      q2Sum += num
      q2.append(num)
    }else {
      let num = q2[q2Idx]
      q2Idx += 1
      q1Sum += num
      q2Sum -= num
      q1.append(num)
    }
    result += 1
  }
  return result
}

❌ 틀린 이유 및 틀린 부분

숫자의 합이 평균을 만들 수 없는 경우를 처리를 못했다

• A를 B로 옮기고 B를 A로 옮기는 행위를 2번 반복 할때까지 만들지 못하면 이건 만들 수 없는 상황이다

Array.removeFirst()의 사용

• Array RemoveFirst는 시간을 엄청 잡아먹는다

⏳ 시간 복잡도

O(N) - 큐의 첫 원소에서 비교가 이루어지기 때문에 2차 반복으로 넘어가지 않는다

📌 풀이 또는 기억할 정보