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

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

프로그래머스

파이썬

투 포인터와 구간합을 이용해 풀 수 있습니다. 

문제를 처음 읽을 때 다음 부분에서 오해를 했습니다.
"한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다."
원소를 pop했으면
그 원소를 다른 큐에 바로 insert 해줘야 하기 때문에
이 과정을 작업 1회로 한다는 말이며,
문제의 표현이 맞는데 ....
제 생각의 흐름은 엉뚱한 곳으로... 

 

간단하게 풀기 위해, 
두 큐를 합쳐서 하나의 큐로 만들었으며,
대신 출발점(left, right)을 각각의 큐의 원 시작점(0, len(queue1))으로 설정했습니다. 

구간합이 전체 원소의 1/2가 되면 성공입니다. 
totals에 구간합을 저장했습니다. 
포인터를 이동할 때마다 카운트를 하나씩 올려줬습니다. 

def solution(queue1, queue2):
    total = 0
    totals = [0]
    for each in queue1 + queue2:
        total += each
        totals.append(total)
    goal = totals[-1] / 2
    count, left, right = 0, 0, len(queue1)
    while left <= right < len(totals):
        if (total := totals[right] - totals[left]) < goal:
            right += 1
            count += 1
        elif total > goal:
            left += 1
            count += 1
        else:
            return count
    return -1

테스트 1 〉	통과 (0.01ms, 10MB)
테스트 2 〉	통과 (0.00ms, 9.96MB)
테스트 3 〉	통과 (0.01ms, 9.94MB)
테스트 4 〉	통과 (0.01ms, 10.1MB)
테스트 5 〉	통과 (0.03ms, 10.1MB)
테스트 6 〉	통과 (0.04ms, 9.96MB)
테스트 7 〉	통과 (0.07ms, 10.2MB)
테스트 8 〉	통과 (0.15ms, 10.1MB)
테스트 9 〉	통과 (0.19ms, 10.2MB)
테스트 10 〉	통과 (0.48ms, 10.3MB)
테스트 11 〉	통과 (32.51ms, 18.7MB)
테스트 12 〉	통과 (14.79ms, 18.4MB)
테스트 13 〉	통과 (15.55ms, 17.4MB)
테스트 14 〉	통과 (16.89ms, 18.4MB)
테스트 15 〉	통과 (20.86ms, 25.4MB)
테스트 16 〉	통과 (22.29ms, 26.6MB)
테스트 17 〉	통과 (21.94ms, 25.9MB)
테스트 18 〉	통과 (60.94ms, 57.8MB)
테스트 19 〉	통과 (68.31ms, 67.9MB)
테스트 20 〉	통과 (92.29ms, 71MB)
테스트 21 〉	통과 (84.12ms, 71.6MB)
테스트 22 〉	통과 (126.45ms, 71.5MB)
테스트 23 〉	통과 (111.62ms, 72.1MB)
테스트 24 〉	통과 (135.14ms, 71.9MB)
테스트 25 〉	통과 (0.11ms, 10MB)
테스트 26 〉	통과 (0.04ms, 10.2MB)
테스트 27 〉	통과 (0.04ms, 10.1MB)
테스트 28 〉	통과 (66.78ms, 29MB)
테스트 29 〉	통과 (2.02ms, 11.5MB)
테스트 30 〉	통과 (75.06ms, 30MB)

 

for 문은 리스트 컴프리헨션을 이용해서 줄일 수 있습니다.
하지만, 초기값 0이 문제였습니다.

reduce 함수로 초기값을 지정할 수 있습니다.
하지만, 추가 모듈을 불러오는 건 보기 싫죠. 

'리스트'와 '제너레이터 익스프레션'을 이용했습니다.  
파이썬 3.8의 귀여운 '바다코끼리 연산자(:=)' 도 사용했고... 
'애스터리스크(*) 연산자'로 '언패킹'도... 

def solution(queue1, queue2):
    total = 0
    totals = [0, *(total := total + each for each in (*queue1, *queue2))]
    goal = totals[-1] / 2
    count, left, right = 0, 0, len(queue1)
    while left <= right < len(totals):
        if (total := totals[right] - totals[left]) < goal:
            right += 1
            count += 1
        elif total > goal:
            left += 1
            count += 1
        else:
            return count
    return -1

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.3MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.04ms, 10.3MB)
테스트 7 〉	통과 (0.05ms, 10.3MB)
테스트 8 〉	통과 (0.08ms, 10.3MB)
테스트 9 〉	통과 (0.18ms, 10.2MB)
테스트 10 〉	통과 (0.41ms, 10.4MB)
테스트 11 〉	통과 (32.60ms, 18.3MB)
테스트 12 〉	통과 (14.02ms, 18.3MB)
테스트 13 〉	통과 (12.27ms, 17.8MB)
테스트 14 〉	통과 (14.11ms, 18.9MB)
테스트 15 〉	통과 (18.93ms, 24.8MB)
테스트 16 〉	통과 (17.22ms, 25.9MB)
테스트 17 〉	통과 (17.55ms, 25.1MB)
테스트 18 〉	통과 (61.84ms, 60.1MB)
테스트 19 〉	통과 (69.91ms, 68.9MB)
테스트 20 〉	통과 (92.55ms, 71.5MB)
테스트 21 〉	통과 (125.80ms, 71.7MB)
테스트 22 〉	통과 (127.28ms, 71.7MB)
테스트 23 〉	통과 (110.70ms, 72.1MB)
테스트 24 〉	통과 (133.11ms, 71.9MB)
테스트 25 〉	통과 (0.11ms, 10.2MB)
테스트 26 〉	통과 (0.04ms, 10MB)
테스트 27 〉	통과 (0.04ms, 10.2MB)
테스트 28 〉	통과 (67.09ms, 28.4MB)
테스트 29 〉	통과 (1.81ms, 11.8MB)
테스트 30 〉	통과 (75.88ms, 30.7MB)

 

itertools를 사용해 보았습니다. 
전반적으로 더 빠르군요... 

from itertools import chain, accumulate


def solution(queue1, queue2):
    totals = tuple(accumulate(chain(queue1, queue2), initial=0))
    goal = totals[-1] / 2
    count, left, right = 0, 0, len(queue1)
    while left <= right < len(totals):
        if (total := totals[right] - totals[left]) < goal:
            right += 1
            count += 1
        elif total > goal:
            left += 1
            count += 1
        else:
            return count
    return -1

테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.1MB)
테스트 3 〉	통과 (0.01ms, 10.3MB)
테스트 4 〉	통과 (0.01ms, 10.3MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.03ms, 10.2MB)
테스트 7 〉	통과 (0.03ms, 10.2MB)
테스트 8 〉	통과 (0.07ms, 10.1MB)
테스트 9 〉	통과 (0.09ms, 10.3MB)
테스트 10 〉	통과 (0.22ms, 10.4MB)
테스트 11 〉	통과 (28.32ms, 18.2MB)
테스트 12 〉	통과 (9.90ms, 17.9MB)
테스트 13 〉	통과 (6.63ms, 16.6MB)
테스트 14 〉	통과 (7.79ms, 17.6MB)
테스트 15 〉	통과 (11.27ms, 24.5MB)
테스트 16 〉	통과 (9.95ms, 25.6MB)
테스트 17 〉	통과 (12.72ms, 24.7MB)
테스트 18 〉	통과 (28.72ms, 53.6MB)
테스트 19 〉	통과 (38.64ms, 63.8MB)
테스트 20 〉	통과 (59.07ms, 67MB)
테스트 21 〉	통과 (51.56ms, 67.8MB)
테스트 22 〉	통과 (93.35ms, 67.9MB)
테스트 23 〉	통과 (81.81ms, 71MB)
테스트 24 〉	통과 (105.14ms, 71.1MB)
테스트 25 〉	통과 (0.06ms, 10.1MB)
테스트 26 〉	통과 (0.04ms, 10.2MB)
테스트 27 〉	통과 (0.05ms, 10.2MB)
테스트 28 〉	통과 (57.72ms, 27.7MB)
테스트 29 〉	통과 (0.93ms, 11.6MB)
테스트 30 〉	통과 (69.56ms, 28.7MB)

 

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Stream;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int count = 0, left = 0, right = queue1.length;
        long goal, total = 0;
        
        var totals = new ArrayList<Long>(1 + queue1.length + queue2.length);
        totals.add(0L);
        for (var each : Stream.concat(Arrays.stream(queue1).boxed(), Arrays.stream(queue2).boxed()).toArray(Integer[]::new)) {
            total += each;
            totals.add(total);
        }
        
        goal = totals.get(totals.size() - 1) / 2;
        
        while (left <= right && right < totals.size()) {
            total = totals.get(right) - totals.get(left);
            if (total < goal) {
                right++;
                count++;
            } else if (total > goal) {
                left++;
                count++;
            } else {
                return count;
            }
        }
        return -1;
    }
}

import java.util.ArrayList;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int count = 0, left = 0, right = queue1.length;
        long goal, total = 0;
        var queue = new int[queue1.length + queue2.length];
        var totals = new ArrayList<Long>(1 + queue.length);

        System.arraycopy(queue1, 0, queue, 0, queue1.length);
        System.arraycopy(queue2, 0, queue, queue1.length, queue2.length);

        totals.add(0L);
        for (var each : queue) {
            total += each;
            totals.add(total);
        }

        goal = totals.get(totals.size() - 1) / 2;

        while (left <= right && right < totals.size()) {
            total = totals.get(right) - totals.get(left);
            if (total < goal) {
                right++;
                count++;
            } else if (total > goal) {
                left++;
                count++;
            } else {
                return count;
            }
        }
        return -1;
    }
}

동빛나님의 설명이 좋아서 퍼왔습니다. 

https://www.youtube.com/watch?v=rI8NRQsAS_s