[프로그래머스] 두 큐 합 같게 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=swift

프로그래머스

 

접근

---

• 각 큐의 원소 합이 같아질 때까지 pop과 insert를 반복
  → 큐1을 타겟으로 하여 기준 값과 비교
• pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가
  → 포인터 사용
• 큐1과 큐2는 각 큐 내에서의 순서가 보장된 상태로 원소를 하나씩 추가/삭제해나간다
  → 큐1 뒤에 큐2의 원소가 하나씩 붙게 된다
  → 최대 길이 상태는 큐1+큐2 인 경우이므로, 큐1과 큐2를 합쳐 포인터로 하나의 배열로 관리한다

 

로직

---

• 큐1과 큐2의 원소 총합이 홀수라면 -1을 반환하여 빠른 종료시킨다
• 큐1과 큐2를 합쳐 하나의 배열을 만든다
• p1이 p2보다 작을 때까지, 그리고 p2가 배열의 길이보다 작을 때까지 반복문을 수행한다
  • p2가 배열의 길이와 같아진다면 원래의 큐1과 동일해지기 때문이다
• 현재 큐1의 총합이 기준값보다 작다면, 큐2의 원소를 더해준다
• 현재 큐1의 총합이 기준값과 같다면, 반복문을 종료하고 answer를 반환한다
• 현재 큐1의 총합이 기준값보다 크다면, 큐1의 원소를 하나 제거한다

 

코드

---

 

1. Swift 풀이

---

import Foundation

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    
    var sum1 = queue1.reduce(0){ $0 + $1 }
    let totalSum = sum1 + queue2.reduce(0){ $0 + $1 }
    if totalSum % 2 != 0 {
        return -1
    }
    
    let queue = queue1 + queue2
    var p1 = 0, p2 = queue1.count
    var answer = 0
    
    while p1 < p2 && p2 < queue.count {
        if sum1 < totalSum/2 {
            sum1 += queue[p2]
            p2 += 1
        }
        else if sum1 == totalSum/2  {
            return answer
        }
        else {
            sum1 -= queue[p1]
            p1 += 1
        }
        answer += 1
    }
    
    return -1
}

 

2. Python 풀이

---

def solution(queue1, queue2):
    
    # 총합이 홀수이면 -1을 반환한다.
    totalSum = sum(queue1) + sum(queue2)
    if totalSum % 2 != 0:
        return -1
    
    answer = 0
    p1 = 0
    p2 = len(queue1)
    queue = queue1 + queue2
    sum1 = sum(queue1)
    
    while p1 < p2 and p2 < len(queue):
        
        if sum1 < totalSum//2:
            sum1 += queue[p2]
            p2 += 1
        elif sum1 == totalSum//2:
            return answer
        else:
            sum1 -= queue[p1]
            p1 += 1
        
        answer += 1
    
    return -1