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

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

프로그래머스

 

내 코드

from collections import deque

def solution(queue1, queue2):
    cnt = 0
    q1 = deque(queue1)
    q2 = deque(queue2)
    q1_sum = sum(q1)
    q2_sum = sum(q2)
    
    for _ in range(int(len(q1)*3)):
        if q1_sum > q2_sum:
            q1_sum -= q1[0]
            q2_sum += q1[0]
            q2.append(q1.popleft()) 
            cnt += 1
        elif q1_sum < q2_sum:
            q1_sum += q2[0]
            q2_sum -= q2[0]
            q1.append(q2.popleft())
            cnt += 1
        else:
            return cnt
            
    return -1

---

 

Review

문제의 유형은 greedy인 것 같다.

sum(queue1) 와 sum(queue2)를 비교했을 때,

sum(queue1) > sum(queue2) 이면 queue1의 원소를 queue2로 넘겨주는 식으로 알고리즘을 짰다.

입출력 예를 이런 식으로 계산했더니 딱 맞아서 이 방식으로 코드를 짜게 되었다.

 

문제를 풀면서 막힌 점이 두가지가 있었다.

1. 반복문의 크기

처음에는 반복문 최대 연산을 len(q1) * 2로 단순하게 생각하였다.

하지만 여러 반례가 존재해서 len(q1) * 3으로 했어야 했다.

여러 번을 돌린 결과 int(len(q1)*2.6) 까지 가능 하다.

 

 

2. for 문 안에 있는 if문 에서의 반복적인 sum 연산

원래는 미리 q1_sum 과 q2_sum을 만들지 않았었다.

그냥 간단하게

sum(q1) 과 sum(q2)를 하여 반복문(for 문) 안에서 계속 sum 연산이 적용되도록 짰었다.

하지만 시간 초과로 인해 조금 코드를 수정하였더니 시간 초과가 해결되었다.

 

q1_sum -= q1[0]
q2_sum += q1[0]

간단하게 이런 식으로 빼고 더해주는 연산으로 해결하였다.