[Programmers] 두 큐 합 같게 만들기

문제

 

입출력 예시

 

풀이

핵심은 양쪽에서 접근할 수 있는 deque을 사용하는 것과 반복문을 빠져나오는 시점을 정해주는 것이었다. 반복문 탈출 조건을 놓치면 무조건 오답이 나오기 때문!

 

※ 기본 아이디어: 원소 총 합이 큰 리스트에서 작은 리스트로 원소를 옮김

 

1️⃣ 특정 TC에서 실패한 코드(11번, 28번)

 

1. 각 queue를 deque으로 바꾸고 리스트 총 합을 미리 구해둔다. 

2. sum(queue1), sum(queue2)을 비교하면서 큰 곳에서 작은 곳으로 값 이동 → 큰 곳에서 popleft()

3. 값이 이동할 때마다 cnt += 1

4. 두 리스트의 합이 같아지면 break

 

위의 로직대로 했고 크게 잘못된 부분이 없다고 생각했는데 특정 TC에서 계속 실패하길래 고민을 꽤나 했다. '질문하기'에서 찾은 반례로 통과할 수 있었다.

 

from collections import deque

def solution(queue1, queue2):
    q1 = deque(queue1)
    q2 = deque(queue2)
    
    q1_sum = sum(q1)
    q2_sum = sum(q2)
    
    total = (q1_sum+q2_sum)//2

    cnt = 0
    
    # 어떻게 해도 total을 만들 수 없는 경우
    if max(q1) > total or max(q2) > total:
        return -1
    
    while q1 and q2:
        if q1_sum > q2_sum:
            popped = q1.popleft()

            q1_sum -= popped
            q2_sum += popped
            
            cnt += 1
        elif q1_sum < q2_sum:
            popped = q2.popleft()
            
            # 없을 경우 입출력 예시 2번에서 6 출력. 7 되기 전에 queue가 비는 경우가 생겨서 방지용
            q1.append(popped)
            
            q1_sum += popped
            q2_sum -= popped
            
            cnt += 1
        else:
            break
        
    return cnt

 

2️⃣ 통과 코드

 

실패 코드와 가장 크게 다른 점은 반복문 탈출 조건이 하나 더 추가됐다는 것이다.

 

[반례]

queue1 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 10]

queue2 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

 

위의 리스트들로 VSCODE에서 테스트했더니 cnt 값이 20 정도였던 것 같다. append를 q1에서만 했기 때문에 q2가 비는 경우가 생기면 while문을 바로 빠져나오기 때문에 cnt 값이 이상하게 나와서 실패하는 케이스였다.

 

아래 2가지를 추가해서 코드를 수정했다.

 

① q2에도 append 추가 → cnt가 제대로 카운트 되기 전에 queue가 비게 되어 while문을 탈출하지 않도록 하기 위한 목적

② ⭐ cnt 값이 계속 증가해 len(queue1)*4와 같아질 경우 -1 return ⭐

 

👀 len(queue1)*4 의미

queue1과 queue2의 원소가 바뀌는 과정이 len(queue1)*2만큼 진행되면 queue1과 queue2의 원소가 완전히 바뀌게 된다. 그 상태에서 원소를 다시 len(queue1)*2만큼 바꾸면 초기 상태와 똑같아지기 때문에 결국 두 리스트의 총 합이 같아지는 경우가 없다는 것을 의미한다. 중간에 합이 같아지는 구간이 있어서 while문을 빠져나오지 못하고 계속 원소만 바꾸다가 바꾼 횟수가 len(queue1)*4와 같아지면 -1을 리턴한다.

 

from collections import deque

def solution(queue1, queue2):
    q1 = deque(queue1)
    q2 = deque(queue2)
    
    q1_sum = sum(q1)
    q2_sum = sum(q2)
    
    total = (q1_sum+q2_sum)//2

    cnt = 0
    
    if max(q1) > total or max(q2) > total:
        return -1
    
    while q1 and q2:
        if q1_sum > q2_sum:
            popped = q1.popleft()
            
            q2.append(popped)
            
            q1_sum -= popped
            q2_sum += popped
            
            cnt += 1
        elif q1_sum < q2_sum:
            popped = q2.popleft()
            
            q1.append(popped)
            
            q1_sum += popped
            q2_sum -= popped
            
            cnt += 1
        else:
            break
        
        ######## 추가한 부분 ########
        if cnt == len(q1)*4:
            cnt = -1
            break
            
    return cnt