[프로그래머스] 두 큐의 합 같게 만들기 | 파이썬 덱과 리스트의 연산 속도 차이 | LV2, python, 2022 KAKAO TECH INTERNSHIP

 

 

프로그래머스의 '두 큐의 합 같게 만들기' 문제입니다.

두 큐의 합이 같아질 때까지 push, pop을 해야 하는 최소 연산 개수를 구하는 문제입니다.

 

합이 더 큰 큐에서 pop하여 더 작은 큐로 push 해주는 것을 두 큐의 합이 같아질 때까지 반복하면 됩니다. 이때, 연산 개수가 전체 숫자의 개수 * (3/2)가 넘어가면 결국 두 개의 큐가 원래 상태로 되돌아 오기 때문에 합을 절대로 같게 만들 수 없다는 의미입니다. 이 때는 -1을 리턴하고 같아질 때까지 push pop 연산을 하며 연산 횟수만 1씩 늘려가주면서 최종적으로 연산 횟수를 리턴해주면 됩니다.

 

알고리즘 자체는 간단한데, 계속 시간 초과가 났습니다.

처음에는 while문을 반복할 때마다 큐의 합을 sum() 함수로 계속 새로 계산해주었습니다. 하지만 이렇게 하면 당연히 queue의 모든 원소를 한 바퀴씩 돌아야 하니 시간복잡도가 $O(n)$입니다.

# -*- coding: utf-8 -*-
# 프로그래머스 두 큐 합 같게 만들기

def solution(queue1, queue2):

	answer = 0

	s1 = sum(queue1)
	s2 = sum(queue2)

	while s1 != s2:

		if answer >= (len(queue1) + len(queue2))/2*3:
			return -1

		if s1 > s2:
			n = queue1.pop(0)
			queue2.append(n)
			answer += 1
		else:
			n = queue2.pop(0)
			queue1.append(n)
			answer += 1
            
        s1 = sum(queue1)
        s2 = sum(queue2)

	return answer

 

 

 

따라서 sum() 함수를 사용하는 것은 처음에 한 번만 해주고, while문을 돌면서는 계산한 합에 옮긴 숫자만큼 빼주고 더해주도록 합니다.

# -*- coding: utf-8 -*-
# 프로그래머스 두 큐 합 같게 만들기

def solution(queue1, queue2):

	answer = 0

	s1 = sum(queue1)
	s2 = sum(queue2)

	while s1 != s2:

		if answer >= (len(queue1) + len(queue2))/2*3:
			return -1

		if s1 > s2:
			n = queue1.pop(0)
			queue2.append(n)
            s1 -= n
            s2 += n
			answer += 1
		else:
			n = queue2.pop(0)
			queue1.append(n)
            s1 += n
            s2 -= n
			answer += 1

	return answer

 

 

 

하지만 이렇게 해도 여전히 시간 초과로 실패했습니다.

 

 

 

문제는 리스트로 push, pop 연산을 했기 때문인데요, 아래 두 개의 이미지는 deque와 list 연산의 시간복잡도를 나타낸 표입니다. 보면 deque의 append와 pop 연산의 시간복잡도는 $O(n)$인데, list의 pop(0)과 append의 시간복잡도는 $O(n)$입니다.

Deque 연산 시간복잡도

list 연산 시간 복잡도

 

이렇게 시간복잡도에서 차이가 나는 이유는 무엇일까요?

deque는 Double-End Queue로 양 끝 모두에서 push, pop연산이 가능한 자료구조입니다. 따라서 push, pop 연산의 시간복잡도가 $O(1)$이 됩니다.

그에 반해 list는 파이썬에서 고정된 사이즈를 갖는 배열이기 때문에 첫번째 원소를 삭제하면 나머지 원소를 모두 하나씩 앞으로 이동해야 합니다. 따라서 첫번째 원소에 push, pop을 하는 경우는 시간복잡도가 $O(n)$이 됩니다. (마지막 위치에 push, pop을 하는 경우는 deque와 list의 시간복잡도 차이가 없습니다.)

 

deque의 push, pop 연산

list에서 첫번째 원소 삭제(pop(0))

[파이썬] 덱 vs 리스트 속도 차이? (deque vs list speed 차이)

 

 

 

최종적으로 아래 코드로 제출하니, 모든 테스트 케이스가 시간초과없이 통과했습니다.

# -*- coding: utf-8 -*-
# 프로그래머스 두 큐 합 같게 만들기

from collections import deque

def solution(queue1, queue2):

	answer = 0
	queue1 = deque(queue1)
	queue2 = deque(queue2)

	s1 = sum(queue1)
	s2 = sum(queue2)

	while s1 != s2:

		if answer >= (len(queue1) + len(queue2))/2*3:
			return -1

		if s1 > s2:
			n = queue1.popleft()
			queue2.append(n)
			s1 -= n
			s2 += n
			answer += 1
		else:
			n = queue2.popleft()
			queue1.append(n)
			s1 += n
			s2 -= n
			answer += 1

	return answer