[프로그래머스] 2022 카카오 테크 인턴십 - 두 큐 합 같게 만들기

문제

 

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

 

예시 코드

def solution(queue1, queue2):
    sum1, sum2 = sum(queue1), sum(queue2)
    target = (sum1 + sum2) // 2
    
    if (sum1 + sum2) % 2 != 0:
        return -1
    
    combined = queue1 + queue2
    start, end = 0, len(queue1)
    cnt = 0
    
    while start < len(combined) and end <= len(combined):
        if sum1 == target:
            return cnt
        
        if sum1 < target and end < len(combined):
            sum1 += combined[end]
            end += 1
        else:
            sum1 -= combined[start]
            start += 1
        cnt += 1
            
    return -1

 

풀이

두 큐의 원소의 합이 같아질 때까지 필요한 최소 작업 횟수를 구하는 문제입니다.

 

로직은 아래와 같습니다.

1. 두 큐의 합을 구합니다. 합이 홀수인 경우 조건을 만족 못 하므로 -1을 반환합니다.
2. 두 큐를 합쳐 하나의 큐로 만듭니다.
3. 슬라이딩 윈도우 방식을 이용하여 두 큐의 합이 같아질 때까지 start와 end 포인터를 이동시키며 cnt를 증가시킵니다.
4. 조건을 만족한다면, 현재까지의 작업 횟수인 cnt를 반환합니다
5. 루프가 끝날 때까지 조건을 만족 못 하면 -1을 반환합니다.