[Programmers] 두 큐 합 같게 만들기

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

프로그래머스

📍 제한 사항

• 1 ≤ queue1 의 길이 = queue2 의 길이 ≤ 300,000
• 1 ≤ queue1 의 원소, queue2 의 원소 ≤ 109
• 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

 

제한사항을 보면 queue1 과 queue2의 길이가 매우 긴 것을 알 수 있다.

 

사실 적절한 알고리즘이 떠오르지 않아 일단 생각나는대로 코드를 짰더니

# 두 큐의 합이 같도록
# 하나의 큐 골라 추출, 추출한 원소 다른 큐에

# 필요한 작업으 최소 횟수 구하기
# 모든 값의 합 구해서 나누기 2 (절반)
# 절반보다 크면 pop, insert / 비교

def solution(queue1, queue2):
    answer = 0
    total = sum(queue1) + sum(queue2)
    half = int(total/2)

    while True:
        if sum(queue1) == half:
            break
        if sum(queue2) > half:
            queue1.append(queue2.pop(0))
            answer += 1
        if sum(queue1) > half:
            queue2.append(queue1.pop(0))
            answer += 1
        if answer == len(queue1)*2 or answer == len(queue2)*2:
            answer = -1
            break
            
    return answer

테케는 맞았으나, 당연히 제출했을 땐 여러 케이스에서 시간초과가 발생했다.

 

그럼 풀이를 한 번 봐보자.

https://velog.io/@isayaksh/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Programmers-%EB%91%90-%ED%81%90-%ED%95%A9-%EA%B0%99%EA%B2%8C-%EB%A7%8C%EB%93%A4%EA%B8%B0-Python

[알고리즘] Programmers 두 큐 합 같게 만들기 #Python

일단, 중요한건 리스트보다는 덱 자료형을 사용하는게 더 좋다는 것이다.

리스트는 0인덱스를 삭제할 경우 모든 데이터를 앞으로 한 칸씩 옮겨줘야 해서 효율적이지 않다.

항상 해당 자료형의 특성을 생각하고 어떤걸 쓰는게 더 효율적인지 생각할 줄 알아야 한다.

만약 큐 크기*3 횟수를 시행하고도 같아지지 않는다면 -1을 반환한다.

-> 이 부분을 전혀 생각하지 못했다. (참고 : https://velog.io/@ynoolee/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%91%90-%ED%81%90-%ED%95%A9-%EA%B0%99%EA%B2%8C-%EB%A7%8C%EB%93%A4%EA%B8%B0)

그리고 for문 안에 sum()을 사용해주면 시간초과가 난다.

 

그래서 정답 코드는?

from collections import deque

def solution(queue1, queue2):
    answer = 0
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    length = len(queue1)
    sum1 = sum(queue1)
    sum2 = sum(queue2)

    for _ in range(length*3):
        if sum1 == sum2:
            return answer
        if sum1 > sum2:
            sum1 -= queue1[0]
            sum2 += queue1[0]
            queue2.append(queue1.popleft())
            answer += 1
        else:
            sum1 += queue2[0]
            sum2 -= queue2[0]
            queue1.append(queue2.popleft())
            answer += 1
    
    return -1

배운점

- for문 안에 sum()을 되도록이면 사용하지 않는게 좋다. 계속해서 바뀐 값의 총 합을 확인해봐야 한다면 위 처럼 for문 바깥에서 sum을 계산한 후에 그 값에서 +나 -를 해주는게 시간 복잡도 측면에서 훨씬 유리하다 !!

- 인덱스를 이용해 삭제가 빈번할 경우 배열(리스트)는 시간복잡도 측면에서 좋지 않다.