[프로그래머스] Lv2. 두 큐 합 같게 만들기(by Python) - 카카오 2번 문제

문제

코딩테스트 연습 - 두 큐 합 같게 만들기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

풀이

어렵지 않은 문제

• 각 배열의 합과, 목표값인 (두 개 배열 합) / 2를 구한다.
• 각 배열을 deque에 넣어 큐로 만든다.
• while문으로 하나의 배열이 목표값에 도달할 때 까지 반복한다.
  • while문 반복 횟수가 (하나의 큐의 길이) * 4와 같아지면, 이 케이스는 반으로 나눠질 수 없으니 -1리턴
    • why? (queue1 모두 pop 갯수) + (queue2 모두 pop 갯수) + (queue1과 queue2서로 pop&append)
  • queue1의 합이 queue2의 합보다 작으면, queue2에서 pop하여 queue1에 넣어준다. 
  • queue1의 합이 queue2의 합보다 크면, queue1에서 pop하여 queue2에 넣어준다.
  • 단, 큐가 달라질 때마다 sum함수를 사용하면 시간초과난다. (sum함수의 시간복잡도는 O(n)이므로)
    • 각 큐의 sum을 먼저 구한 후, pop하면 -, append하면 +로 단순 더하기 빼기로 계산한다.

 

코드

from collections import deque

def solution(queue1, queue2): 
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    
    total = sum1 + sum2
    half = total // 2
    
    count = 0
    len_queue = len(queue1)
    while True:
        if count == len_queue * 4:
            return -1
        if sum1 < half:
            target = queue2.popleft()
            sum1 += target
            sum2 -= target
            queue1.append(target)
            
        elif sum1 == half:
            break
        else:
            target = queue1.popleft()
            sum1 -= target
            sum2 += target
            queue2.append(target)
        count += 1
            
        
    return count

 

 

[카카오 코테 공식 해설] 

https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

2022 테크 여름인턴십 코딩테스트 해설