[2022 KAKAO TECH INTERNSHIP] 두 큐 합 같게 만들기

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

프로그래머스

 

풀이

두 큐의 합을 같게 만들어주려면, 합이 더 큰 큐에서 pop해가면서 중간값을 맞춰봐야 최소횟수.

이 과정에서 완전히 빈 큐가 생겨버리면 두 큐의 합을 같게 만들 수 없는 것이므로 -1을 리턴해주면 된다.

로직 자체는 맞게 접근한 것 같은데 테스트케이스 몇개가 계속 시간초과가 나서 파이썬 메서드의 시간복잡도를 봤더니 답이 나왔다.

 

배열의 가장 앞의 요소를 pop해주기 위해 배열 자료형의 pop(0) 메서드를 사용했는데, pop() 연산 자체는 복잡도가 O(1)인데 pop(0)은 O(n)이다. 그 이유는 맨 앞에 있는 값을 출력해주기 위해 전체 복사를 하기 때문이다..! 따라서 리스트 말고 deque를 사용하여 pop(0) 대신 popleft()를 사용하는 것이 시간복잡도 상 매우 유리하다.

 

자료형을 list -> deque로 바꾸고 테스트케이스 22~24번이 해결됬으며,

최대 가능한 횟수를 모든 요소끼리 서로 다 바꿔도 안될 때 (리스트의 최대길이만큼 교환했을 때) 300,000번으로 제한해두니 테스트케이스 11, 28번이 해결되었다.

 

sum() 메서드와 len() 메서드 역시 매번 연산해줄 필요는 없어서 산술연산만 할 수 있게 코드를 약간 길게 적었다.

 

방향은 맞게 잡았는데 시간복잡도에서 30분은 더 쓴 듯 하다.

 

python 코드

from collections import deque
def solution(queue1, queue2):
    answer = 0
    
    deque1 = deque(queue1)
    deque2 = deque(queue2)
    
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    
    len1 = len(queue1)
    len2 = len(queue2)
    
    goal = (sum1 + sum2) / 2
    
    while len1 != 0 and len2 != 0:
        if sum1 == goal and sum2 == goal:
            return answer
        
        if answer > 300000:
            break
            
        if sum1 > sum2:
            value = deque1.popleft()
            deque2.append(value)
            sum1 -= value
            sum2 += value
            len1 -= 1
            len2 += 1
        elif sum1 < sum2:
            value = deque2.popleft()
            deque1.append(value)
            sum1 += value
            sum2 -= value
            len1 += 1
            len2 -= 1
        else:
            if sum1 == goal and sum2 == goal:
                return answer
            
        answer += 1
    
    answer = -1
            
    return answer