[프로그래머스/Python] Level 2_두 큐 합 같게 만들기(2022 KAKAO TECH INTERNSHIP)

📌문제 유형

2022 KAKAO TECH INTERNSHIP (구현)

 

📌문제

프로그래머스

 

📌나의 문제풀이

- queue1에서 꺼낸 것 q1_sum에서 빼고, queue2에 넣은 것 q2_sum에 더하기

• queue1, queue2 변동 될 때마다 sum(queue1), sum(queue2) 비교하면 시간복잡도 O(n)으로 시간초과 남
• q1_sum, q2_sum을 이용하여 값만 더하고 빼면 시간복잡도 O(1)

from collections import deque

def queue_pop(queue1, queue2, q1_sum, q2_sum):
    num = queue1.popleft()
    queue2.append(num)
    q2_sum += num
    q1_sum -= num

    return q1_sum, q2_sum
    
def solution(queue1, queue2):
    answer = 0
    ans_sum = (sum(queue1) + sum(queue2)) // 2
    q1_sum, q2_sum = sum(queue1), sum(queue2)
    
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    len_ = len(queue1)
    
    while (answer <= 600000):
        if q2_sum == ans_sum:
            break
            
        if len(queue1) == 0 or len(queue2) == 0 or answer == 600000:
            answer = -1
            break
        
        if q1_sum > q2_sum:
            q1_sum, q2_sum = queue_pop(queue1, queue2, q1_sum, q2_sum)
        elif q1_sum < q2_sum:
            q2_sum, q1_sum = queue_pop(queue2, queue1, q2_sum, q1_sum)
            
        answer += 1
            
    return answer

 

📌다른 사람의 문제풀이

- 유사한 풀이 

from collections import deque

def solution(queue1, queue2):
    answer = 0
    mid = (sum(queue1) + sum(queue2)) // 2
    leftSum = sum(queue1)

    queue1 = deque(queue1)
    queue2 = deque(queue2)

    while queue1 and queue2:
        if leftSum > mid:
            tmp = queue1.popleft()
            leftSum -= tmp

        elif leftSum < mid:
            tmp = queue2.popleft()
            leftSum += tmp
            queue1.append(tmp)

        else:
            return answer
        answer += 1

    return -1

 

📌리뷰

- while 값 제한할 때,  answer이 600000 이하인 걸로 제한

• queue1 + queue2의 최대 길이가 600000이기 때문

- sum(queue1)의 시간복잡도는 O(N)이므로 q1_sum, q2_sum으로 숫자 빼기

- Python은 int 길이 초과해도 알아서 long형으로 바뀜! 그래서 오버플로우 가능성 고려하지 않아도 됨 

 

- 문제 조건 잘 읽기

- 시간 초과 나면 시간 복잡도 확인하기...😥